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.
Applications of Binary Trees
- 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.
- 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: