How do Binary Trees work?
Trees are dynamic data structures, meaning that they are created to hold any data and can grow and shrink automatically; unlike Java arrays, which have a fixed size. An important characteristic of Binary Trees is that they are very efficient data structures for searching, insertion and deletion. They are much faster than ArrayLists, Arrays and Linked Lists in terms of searching for an item.
Let’s go over a few terms for binary trees in the following diagrams:
A node
Trees are made up of nodes, just like linked lists. Each node can contain data and a reference to other nodes. The first node on a tree, the one at the top-most position, is called the Root. Any node, including the root node, can have children. This means that the left reference or right reference is not null. A node that has no children is called a leaf. A node that has children is called a parent node.
A set of nodes along a path is a branch. A path is a sequence of nodes. As you travel through a tree looking for specific data you want to follow a specific path. There are different strategies for traversing a tree, which we will discuss in future sections.
| Term | Explanation |
| Children | Nodes below another node. |
| Parent | A node that holds references to other nodes below it. |
| Root | The first node on a tree. It sits at the top-most position. |
| Path | A set of nodes found in a sequence. |
| Branch | A set of nodes found on a path in a manner in which the bottom-most is directly below the next node in the path. |
| Height | The number of levels from the top to the bottom. |
| Level | In a sense, the number of layers found in a tree. The example above has three levels. |
| Subtree | Any node can be considered the root of a subtree. A tree can be composed of many subtrees. |
| Traversing | Visiting all notes in a tree in a specific order. |
| Visiting | Arriving at a node and performing an operation with the data held by the node. |