The concept of a binary tree is one of the most important foundational concepts in programming and computer science. In this article, we'll give a brief introduction to the underlying concepts, show a few visual examples of binary trees, and showcase a small code implementation of a binary tree node, which itself also represents a binary tree.
Binary Trees
A binary tree is a data structure which is composed of nodes. Nodes are connected via parent-child relationships. The root node of the tree has no parents, and every other node has one parent. It is important to note that a node can never have more than one parent, and a tree can never have cycles. Unlike other tree structures, nodes in a binary tree can only have 0, 1, or 2 children. When dealing with binary tree nodes, we can refer to the child nodes as the left child and right child.
Applications of Binary Trees
Binary trees, and specific types of them, have a wide array of applications. A few common examples are shown below:
- Storing data in order: a type of binary tree called a binary search tree can be used to efficiently store data in a particular order and efficiently retrieve items in the tree or check if the tree has that item.
- Representing syntax: language processors and code compilers can read in a piece of text or code and create a binary tree called an abstract syntax tree
- Managing priority queues: storing a queue of items / tasks where some items have higher priority than others.
Tree Nodes
The purpose of a node within a tree is to encapsulate some value, such as a number or string, and in some cases, represent relationships, such as ordering, based on the way it is connected to other nodes. Nodes in a binary tree have the following properties:
- Value: the value this node encapsulates.
- Left Child Node: a node which represent a child of the current node on the "left" side. If the node is not set, this value can be set as null.
- Right Child Node: a node which represent a child of the current node on the "right" side. If the node is not set, this value can be set as null.
- Parent Node: a node can have a reference to its parent as well, but this is generally not used in tree implementations, as this reference is not required for most tree algorithms.
There are two special types of nodes:
- Root Node: the node which exists at the top of the tree. There can only be 0 or 1 root nodes in any given tree. If the tree is empty, there will be 0 root nodes; otherwise, 1 root node.
- Leaf Node: this is a node which has no child nodes. All non-empty trees have at least 1 leaf node.
A few different examples of binary trees are shown below:
Trees and Subtrees
In a tree, a subtree is a portion of the tree which starts on any given node in the tree. For example, in the last image above, the subtree starting with the node marked 245 is a subtree of 7 nodes. As a consequence, if we were to add a node reference to the left node of the node marked 127, and the node we're adding has 2 child nodes itself, we are esentially adding a subtree to our existing tree. If we were to remove the node marked 418, we would be removing a subtree of 3 nodes.
Creating and Modifying Binary Trees
In terms of creating a binary tree, we can actually represent an entire tree with one node reference. However, we will need to write some logic to move through the tree if we want to add or remove nodes. Since we have no restrictions on how our binary tree needs to order or position nodes, we can choose from any number of different algorithms for inserting and deleting binary nodes. The selection will depend upon what we are using the binary tree for, and if we need to dynamically insert into the tree at all. In cases where the structure and nodes are known ahead of time, we can manually create and connect all nodes as needed without using any generic insert method.
Implementing a Binary Tree Node
We can implement a binary tree node with a few getter and setter methods / properties as shown below. In concept, an entire binary tree can be represented in a recursive manner via reference to a single node, that reference being the root node of the tree.
Storing Multiple Values in a Node
In the previous sections, we've discussed nodes which hold a single value, plus the child node references. There may be use cases where we will want each node to hold multiple values, such as a record with fields recordID and recordValue. In this case, both fields together can be considered to be a "single value". In terms of code, the value can be an object, dictionary, array, or custom class. When we visit each node, we can retrieve the object from the node, then operate on it as we normally would with that type of object.
Binary Search Trees
Binary search trees are a special type of binary tree which maintains ordering throughout the tree. This is a very useful data structure which has a wide array of applications. To learn more about binary search trees, please visit our dev page which introduces the concepts and provides code examples: