Now that you're done following along with the lessons to build and traverse a binary search tree, it's time for an additional challenge. Try adding the functionality listed below to your application. It's okay if you do not get the functionality fully implemented - these are both challenging features and there's a reason we don't walk through them in-depth in our curriculum.
At first glance, this may not seem overly challenging - just find and remove a node, right? We already have methods to traverse the tree to insert or find nodes, so why would removing a node be any more difficult?
Well, what happens if you remove a node from the middle of a tree? You can't just leave that space empty - another node needs to replace it, but which one? And once that node is removed, what about filling in the space that moved node left behind?
BST.prototype.remove()method should return
falseif the node to be removed doesn't exist in the tree.
The diagrams below illustrate what happens:
In the left diagram, Node to delete hasn't been deleted yet. We see that it has links to its parent node and two child nodes. All of those connections need to be updated.
In the right diagram, Deleted Node has been removed. Former Left Child used to be Deleted Node's left child - but now it has taken its place. Now, Deleted Node is no longer Former Left Child's parent - instead Parent is. Meanwhile, Former Right Child becomes the right child of Former Left Child.
Think of it as two siblings next in line for succession to be the king. The king dies, then the first child becomes the king. The second child is next in line for succession. Any other children of those two children still need to be accounted for!
Next, we'll move onto another challenging problem. The first couple of steps will be easy to solve, but the problem will get progressively harder. How can we keep a tree balanced? Well, first, we need to think about what it even means for a tree to be balanced. Fortunately, this is actually very easy to do - the difference between the height of the root's left subtree and the height of the root's right subtree needs to be either 1 or 0. We can depict this with an illustration.
Here's an example of a balanced tree with its height:
Here we can see that the height of the left subtree is 1 while the height of the right subtree is 2. The difference between those heights is 1 so this is a balanced tree.
On the other hand, let's review this illustration of an unbalanced tree from a few lessons ago:
The tree above has a left subtree with a height of 0 and a right subtree with a height of 6 - a difference much greater than one. This tree isn't balanced at all!
Having a balanced tree makes it more efficient. It means that the maximum number of iterations a search or insert algorithm has to do is approximately the same for both sides of the tree.
Try writing an algorithm to check a binary search tree's balance - and rebalance it if necessary. Make sure to use TDD. Once again, the first few steps are much easier - but the problem gets progressively harder.
BSTconstructor. One will store the height of the left subtree while the other will store the height of the right subtree. Note: It's considerably harder to compute the height of a tree than to store information about its height. We would need to use a depth-first or breadth-first search to determine the greatest height in a subtree otherwise.
BST.prototype.insertNode()method so that it keeps track of the height of an inserted element. That means that each time the method traverses down a node, the temporary height should be increased by one. If the temporary height is greater than the actual height of the subtree when the element is inserted, the actual height should be updated.
BST.prototype.check()method. This method will just check to see if the tree is balanced or not. It should return the difference in height between the left and right subtrees.
The article is a full walk-through of the process, so you can choose either to follow along with the coding steps in the article or try to solve at least a few steps of the problem on your own. For a greater challenge, we recommend using the article only for hints and trying to solve as many steps without additional assistance.
Lesson 11 of 11
Last updated January 19, 2021