By Elson Correia
Everything about the tree data structure in JavaScript.
You really can’t avoid the tree data structure. Whether you are aware of it or not, tree data structures are almost everywhere. It is the file system in your computer, spellchecks, and keyboard word suggestions, the HTML DOM, your object-oriented class structure, etc. The tree data structure is powerful, flexible, and fun to work with. One that every programmer should feel comfortable using.
Video Version of This Article
This post is an improved and more detailed article version of the Tree Data Structure Series on Youtube that you can check if you prefer videos.
What is a Tree?
The tree data structure is a non-linear abstract data structure that simulates a hierarchical structure of data. It has root, child, and parent nodes similar to a family tree. In other words, the tree is a collection of nodes where each node can contain other nodes as children.
When working with trees, there are a few terms and concepts you need to become familiar with. Here a few you need for now.
- Node: A member of the tree which can be a tree itself.
- Root Node: The topmost node in a tree. The only node in a tree without a parent.
- Branch Node: (also known as an internal node). A node with a child node.
- Leaf Node: (also known as an outer or external node). A node without children.
- Child Node: A node under another node is the child of that node.
- Parent Node: A node with a child node.
- Ancestors Nodes: All parent and their parent nodes.
- Descendant Nodes: All children and their child nodes.
- Sibling nodes: Nodes that share the same parent.
- Subtree: A node and all it's descendant nodes
- Depth of a Node: It is the path of a node towards the root node. Pretty much how many levels of parents upwards.
- Height of a Node: It is the longest path to its lower leaf node. Pretty much how many levels of children downwards.
- Tree traversing: Also known as “walking the tree” is stepping through the nodes of the tree. You iterate a list and traverse a tree.
- Recursion: When a function calls itself. Recursion is a very common way to traverse the tree.
- Ordered Tree: A tree in which its order is specified for each node, for example, in the binary tree the left node has less value than the parent and the right child node has greater value than the parent.
Tree Types
Whenever you are talking about tree types you are normally talking about two categories, ordered or unordered trees. Unordered trees have no constraints on the numbers of children and in which order the nodes should be organized. These are trees like the DOM tree or the file system tree, for example.
Ordered trees have simple to complex sets or rules you must follow. It may dictate how many children a node should have and in which order they must come. It may limit the height a node can reach at all times and even the colors it should use. For the most part, when people are studying trees, they tend to focus on this category of trees which offers more to be explored.
Ordered Trees vary in complexity and some exist to help solve very specific problems. There are so many tree types and some are simply variations of each other. Let’s look at the most basic and popular ones programmers normally start their tree study with.
Binary Tree
A tree in which a node has at most two children which are referred to as left and right “child”. Commonly, there is a rule on which defines on which side the node is inserted. This tree is the most basic ordered tree on which a lot of other tree types are based. The rest of the list that follows are all variations of this tree.
Binary trees can be used to implement sorting and search algorithms and even other data structures like a priority queue or linked list by given certain rules to follow. You can also use an array to represent a binary tree as an implicit data structure. To be honest, almost any data structure can be represented using a binary tree which is a property that simply makes it worth studying.
Binary Search Tree
A binary search tree is a variation of the binary tree used in the famous search algorithm called “binary search”. It adds an additional rule that states that the left node value must be less than the parent value and the right node value must be greater than the parent value. An inverse is also an option.
With the binary search tree, you can implement priority queues, for example, and use it for anything in which there is a constant read and write of values.
AVL Tree
AVL stands for Adelson-Velsky and Landis named after their inventors and it is a binary tree that targets a specific limitation of the binary tree which is the height of nodes. It is part of the category of trees called self-balancing trees. Safe to say that it is an optimized binary tree with a feature that makes binary trees even faster for search.
If you follow the child value rules of a binary search tree, we can continuously insert a node which values are greater than their parent causing the root right child height to increase and making it slower to retrieve the leaf node values, for example. The AVL tree fixes this problem by introducing the concept of “self-balancing” which allows the tree to change its structure to equalize the height of both sides.
In an AVL tree, the root left and right node height differs at most by one. By rebalancing the tree, often time the root node value changes to follow the rule of child values and maintain an optimal search height.
Red Black Tree
A red-black tree is yet another type of self-balancing tree much like an AVL tree. In fact, the AVL tree is considered a subset of RB Tree since you can color it red and black, and would work perfectly. They still differ in few things and should be used for totally different purposes.
AVL is strictly balanced which makes it great for lookups and RB Tree has a relaxed balancing nature which makes it faster for insertion and removal of nodes. This means that RB Tree is better when you perform a lot of inserts and remove operations and AVL is best when you are constantly searching for a particular value.
Red Black Tree has its set of rules around color which makes more sense when you try to implement it. For this tree, every node is either red or black but is inserted as red then gets recolored accordingly after. The root here is always black as well as nill nodes and in case a node is red, all its child nodes must always be black. Lastly, a path from a node to any of its leaf nodes goes through the same number of black nodes.
By these rules, it is saved to assume that if a node is red then its parent must be black and that it contains both of its children which are black. It is also possible to have the entire tree colored black as it does not violate any rule. Because of these extensive rules, the red-black tree is a more elaborated tree to implement than the AVL tree.
Heap Tree (Treap)
A heap tree or treap is a very special binary tree. If you worked with javascript you probably heard of memory heap or heap sort which is a sorting algorithm using the heap tree. In a sense, a heap is a more efficient implementation of a priority queue and often enough people refer to priority queues as heaps.
A heap can only be max or min and is called max-heap or min-heap. A min-heap simply means that the root node value is the smallest value in the tree and if it is a max heap, the root node value is the highest value. The heap is not sorted by default and it is the perfect tree for cases when you are constantly looking for the min or the max value.
This heap property makes it perfect for sorting and graph algorithms since you will be looking for the next value that follows. Same for priority queues where you are constantly grabbing the next value based on priority. Because of these properties, there are many other variants of heap trees to address very specific scenarios and types of data.
variants of heap trees
The array is often used to implement this type of tree as well as a linked list. It is a much simpler tree whose nature makes it a super-fast tree type with the complexity to find the min or max value of O(1).
Trie
A trie, also known as a digital tree, is a type of search tree very commonly used in string search. Although it is a search tree like the binary search tree, they do not work the same way. The nodes do not store their associated keys, instead, they define the key with which they are associated.
A trie for keys “A”, “to”, “tea”, “ted”, “ten”, “i”, “in”, and “inn”. Each complete English word has an arbitrary integer value associated with it.
Whenever you type on your phone and get autocomplete suggestions, it is likely that a Trie was used to make that prediction. It is also used in spell checks and hyphenation which is why I believe you should learn about this type of tree since you likely used applications that take advantage of it.
Its search nature is so powerful that it can be used instead of hash tables with a lot of advantages. It is also used in sort algorithms like the radix-sort and burst-sort. Another Trie type would be the suffix tree which is used to index all suffixes in a text in order to carry out fast full-text searches.
When to use a Tree?
As you were able to read in previous parts of this article, the applications of trees vary a lot. From helping with search and sorting to defining the structure of things, it is safe to say that anything can be represented using a tree data structure with pros and cons. In general, a tree is good for the following reasons:
- There is a type of hierarchical nature in the data itself. A piece of data is contained or can contain others in some type of class and subclass or parent-child relationship.
- You need to make path decisions to search for things or there are many variations of things that you can break down and explore as paths.
- You need to take advantage of the traversing speed instead of the looping nature of a data structure by making decisions along the way for efficiency reasons.
Conclusion
In a sense, learning about tree data structure gives you superpowers. There is so much more to learn and to explore with it that the whole process of exploration is just fun and worthwhile. You can use it for almost anything and a lot around us already take advantage of it as a programmer, studying the tree data structure opens the door for many complex data relationships and concepts.
This is a powerful data structure to explore and become familiar with as it teaches you to think of data in a non-linear fashion and explore decision-making in form of a hierarchical structure.
YouTube Channel: Before SemicolonWebsite: beforesemicolon.com