Data Structures Part 6: Trees
Hello there! Welcome back for our last data structure that we are going to cover in this little series. And we’ve saved the most complex for last…Trees! When visualizing a tree data structure, I like to think of something like the picture above, except inverted. Have you ever wondered how you are able to see everything rendered on a page? This is all done by the DOM (Document Object Model), which is actually just a tree data structure comprised of HTML or XML elements that fill up the page. Or maybe Facebook’s feature to leave comments under a friend’s posts. Last but not least, a family tree, each family member being a node on a tree, leading to more nodes. By the end of this article, we will know more about this data structure, its properties, how to make one from scratch, and most importantly, how to implement them to solve problems. Let’s get started!
What is a Tree?
A tree is a hierarchical data structure that consists of parent and child nodes connected by references or pointers. If this description sounds familiar to you, it is because linked list have a very similar anatomy. Linked lists are actually a type of tree, except they are linear. Visualgo is an amazing resource for visualizing this data structure and getting a feel for the data flow when working with different methods.
Components of a Tree
1. Root — the first node of the tree
2. Parent — a node with any nodes descending from it
3. Child — a descendant from any parent node
4. Sibling — nodes that are on the same level as each other, and descending from the same parent node
5. Leaf — a node without any children
Types of Trees
While there are dozens of existing tree data structures, we are only going to cover one of the most popular versions seen in software development, and that is the Binary Tree.
A Binary Tree is a specific type of tree data structure that contains at most two children for every parent node. There are two types of Binary Trees, and we will observe the differences between the two:
a.) Perfect Binary Tree — all parent nodes have exactly zero or two children, and the bottom level is completely filled. This type of tree is extremely efficient and has two unique properties. First, the number of nodes double as you go from one level to the next. Secondly, the amount of nodes that are on the last level is equal to the sum of all the other nodes plus 1 (which breaks down to approximately half of all the nodes in the entire tree are on the last level).
b.) Full Binary Tree — all parent nodes have either zero or two children, and never just one child. The bottom level does not have to be completely filled.
Trees from Scratch
Now that we have learned the anatomy of a tree, we are going to implement our own binary tree from scratch! The type of binary tree that we will be creating is called a Binary Search Tree, which is the most common subset of a binary tree. It is optimal for searching as well as organizing because it preserves relationships and stores them in a relational manner. When working with binary search trees, there are a couple of rules to keep in mind. The first rule is that all child nodes to the right of the root node must be greater than the root node. The second rule is, all child nodes to the left of the root node must be less than the root node. With that being said, let’s create our first binary search tree!
First, we are going to initialize a Node class. This class will have a constructor with a value for a parameter, as well as three properties: the value of the node itself, a reference to the left child node, and a reference to the right child node.
Now that we have our Node class, we are also going to create a BinarySearchTree class that contains a constructor with a root property. Since we do not have a tree yet, our root property will be set to null.
Our first method will insert a new node into the tree. Our “insert” method will have a value as a parameter. We first want to create a new node object and send the value as an argument. Then we want to check if there is an existing root node, if there is not, then the root node will be set to our newNode we created. If there is an existing root node, then we will move through some logic with a while loop. We want our while loop to run until it has met a specific condition. If the value is less than the current node’s value we are comparing it to, then we want to move left. If the current node’s left property is null, then we will assign current.left to the newNode and return the entire tree. Otherwise, the current node is the current.left, and we can move on to our next condition. If the value is greater than the current node’s value we are comparing, then we want to move right of that node. If the current node’s right property is null, then we will assign the current.right property to the newNode and return the tree. Otherwise, the current node is the current.right property and we can keep traversing through the tree. Awesome! We have successfully added a new node to our tree, let’s move on to our next method.
Now we want to search for a specific value within our tree using this “search” method, which will also have a value as a parameter. First we are going to check if there is a root, if the root is null, then we can return false and we are finished because the tree is empty. If the tree is not empty, we will assign a current value to the root. While there is a current node, we will check a few conditions. If the value we are looking for is less than the value of the current node, then we will assign the current node to current.left. If the value we are looking for is greater than the value of the current node, then we will assign it to current.right. If the value is equivalent to the current value, then we will just return the current node itself. Lastly, if the value we are looking for is not in the tree, then we will return false!
And there you have it! We have built a binary search tree!
Big O Notation and Binary Trees
Binary Search Trees are very efficient when having to search for data. One beautiful characteristic of this data structure is its time complexity of O(log n) for lookup, insert, and delete methods. If you remember, time complexity of O(log n) is almost as efficient as O(1), which is amazing because we are still having to traverse through data instead of knowing exactly where a specific piece of data is located. Binary search trees are designed to only traverse through half the data in the tree rather than having to visit each node. In a worst case scenario however; a binary search tree can have a time complexity of O(n). Can you think of when this would occur? If each node added is consistently larger than the current is when we would start to see O(n) time complexity. Our binary search tree will begin to look like a linked list and in order to find any node requires traversal through each one. This is why it is adamant to keep your binary search tree balanced to prevent this type of behavior.
Examples:
Now that we have built a foundation of binary search trees, let’s branch out and solve a coding challenge (yes, the pun was intended). We are going to find the maximum height of our binary search tree.
Our “maximumHeight” method will take in the root of our tree as the parameter. We will first check if the root is null, if so, the height will return as -1. If the root is not null, then we will move on to our next conditions, which will also define a base case for recursion (which we will go over soon). First, we are going to let a “current” value equal the root. If the current.left value AND the current.right value are both equal to null, then our tree will have a height of 0 (since there is only one node in the tree). If the current.left value is null, then we will call this function on itself and pass in the current.right node as the argument, and then add 1. If the current.right value is null, then we will also call the function on itself, pass the current.left value in as an argument, and then add 1. We are using recursion in this function so we are able to effectively move through the tree without having to call this function for every level manually. Then, we will create two constants, one for the height of the left side of the tree (“leftHeight”), and one for the height of the right side (“rightHeight”), and call our function again with the current value of each as arguments (both “leftHeight” and “rightHeight” will go through each of the conditions defined in our base case until they have reached a leaf node). We finally will return the largest of the two numbers by using the Math.max() method and add 1 to receive the height of the entire tree.
And there you have it! We have found the maximum height of a binary search tree, using recursion!
Well, we have officially reached the end of our data structure journey! As you can see, trees are one of the most complex of all the data structures and for good reason. With tree structures like binary search trees, we are able to accomplish powerful and efficient functionalities. For example, a simple Google search uses a binary search algorithm that returns thousands of websites in seconds ( you can observe this on Google and see the amount of seconds it took in the upper left hand corner just beneath the search bar). While only scratching the surface of tree data structures, I hope that you have a more rooted understanding of them and more importantly how to implement them to solve problems (sorry, one last pun). Thanks for reading, and until next time…
💕👩🏾💻Happy Coding!👩🏾💻💕
RESOURCES:
