Binary Trees

While diving further into coding interview questions this week, I took a deeper look at data structures, particularly trees. In programming, trees are a non-linear data structure, and they instead hierarchically maintain data. Like other structures, however, they are comprised of a bunch of nodes containing data pieces. Every tree has a “root node.” Children nodes are branched off from this root node and connected by edges. Once we traverse to the bottom of a tree, these bottom-level nodes are called leaves. You can picture this data structure as a real-life tree, but the properties are upside down, with the root being on the top vs. the bottom. Every node, other than this root, has one parent. However, they can have a varying amount of children nodes. Children can then have sibling nodes that are horizontal to them and grandparent nodes that are two levels up.

Tree Terminology

• Root — The top node in a tree.
• Child — A node directly connected to another node when moving away from the root.
• Parent — The converse notion of a child.
• Siblings — A group of nodes with the same parent.
• Leaf — A node with no children.
• Edge — The connection between one node and another.

Following the names of parent, sibling, and child, a typical real-life example of this data structure is a family tree. Even if you aren’t familiar with trees, as a programmer, you’ve likely worked with one before, the DOM. The DOM also hierarchically organizes its data (the elements of a web page). There are, however, many different types of trees in programming, and in this article, I will quickly summarize some of the most common Binary trees. The different types of trees we’ll discuss include Binary Search, AVL, and Red-Black trees. Each tree type has its use case and distinctions.

The bare Binary tree’s primary distinction is that each node can have, at most, two children nodes. This tree is one of the most common ways you’ll see data organized in a tree structure, and all the other trees we’ll cover are subsets of this tree. A binary tree can be considered either complete, full, or perfect. A perfect binary tree is when all nodes have two children nodes, and all leaves end at the same level. An example of a complete binary tree would be one with every level filled other than the last. Every node has either 0 or 2 children in a full binary tree. A binary tree is the most basic form of a tree data structure. There are many more types than just the three we’ll cover.

A binary search tree (BST) is an extension of a binary tree with additional restrictions. Like the binary tree, each node still has a max of two children — however, the values and where we position them matter. The left child of the parent should always be less than or equal to that parent node. And vice versa for the right side, it should always be greater than or equal to the parent. The fact that the tree keeps its data organized makes searching operations more efficient, hence the name binary search.

An AVL tree is a self-balancing binary search tree. The name comes from the creators Adelson-Velshi and Landis, who helped create the first tree that balances dynamically. A balancing factor is added to each tree node based on whether the tree is balanced (-1, 0, 1). In this tree, the heights of the two children’s sub-trees can’t differ by more than 1. If the tree gains a new node and causes the heights to vary by more, it’ll be rotated to ensure the tree remains balanced. Access, removal, and insertion with an AVL tree maintain a good Big O runtime of O(log n). The tree is most beneficial when used for lookup operations.

Finally, red-black trees are very similar to AVL trees. A red-black tree is also self-balancing and a subset of the binary search tree. Each node in this tree is either red or black, which is helpful to ensure the tree remains somewhat balanced. When new nodes are inserted or deleted, they will be rearranged to maintain their balance. The balancing isn’t perfect, but it still allows us to expect a decent runtime. This tree maintains a solid runtime complexity of O(log n).

In conclusion, trees notoriously are one of the most powerful data structures. The primary advantages include how it quickly displays data through the hierarchical organization, its efficiency in operations such as searching and insertion, and its flexibility. Trees are most beneficial for showing relationships among various nodes, especially in these binary trees with a limit of two children. The categories of different trees include Binary, B-trees, Heaps, General, Multiway, Space-partitioning, and Application-specific trees. There are numerous types in each tree category, and memorizing them would take an incredible amount of time. However, taking the time to understand some common ones enables you to get a strong feel for use cases and possible coding implementations. Trees aren’t native to JavaScript, but you should consider them in future coding projects!