How to Remove a Node from a BST? by Danny Reina

Intent

To wrap up constructing a basic binary search tree (BST) let's first do a quick no-nonsense review. Take note that you can find my how-tos on building the search & insert methods for a BST here and here.

What is a BST?

A BST is a tree data structure that carries the following foundational principles.

  • nodes can have up to only two children nodes
  • the value of any node is greater than all values occurring in its left subtree and less than all values occurring in its right subtree
  • the left and right children nodes of the node you are positioned on, have to satisfy the BST property
valid BST
not a valid BST

Starting Off

Let's start with some boilerplate code.

  • compare target value to value at current node, return value if equal
  • if target value is less than current node’s value then move to the left child of current node and repeat comparison logic
  • if target value is greater than current node’s value then move to the right child of current node and repeat comparison logic
  • continue until target value equals current node’s value or return false if value not found
finding the target node conceptual drawing. **NOTE** bottom right node of 12 should be 15 NOT 5. Sorry :)
code for finding the target node
keep track of parentNode

Edge Case #1

We will start off by addressing the case when the node we want to remove has two child nodes. So we would have to check if our currentNode has two child nodes and we do so like this.

check if target node has two child nodes
remove node with two child nodes
identify left most node
result
resolved edge case for two child nodes

Edge Case #2

Hang in there, there is a lot to take in but we will get there I promise! The next edge case we will tackle is removing the root node but when it has either only a right child node or only a left child node.

edge case #2 remove root node that only has a right or left child node
targeting root node for removal
check if left or right child node or root node exists
manually change root node value with right child node value
manually replace root node value with value of right child node
manually changing nodes
illustration for currentNode.left = currentNode.right.left
result of currentNode.left = currentNode.right.left
illustration for currentNode.left = currentNode.right.left
result of currentNode.left = currentNode.right.left
resolved edge case #2

Edge Case #3

Our final edge case focuses on removing a node that does not have two children nodes but has either one or no child nodes at all. The child node can be either a left or right child node. This edge case also has two sub-edge cases.

edge case #3
don’t leave me
check if the node to be removed is on the right branch of its parent node
check if node to be removed has a left or right child node or any at all
result for sub-edge case #1 for edge case #3
resolve sub-edge case #2
final code for the remove method in a BST
find the smallest value

Time Space Complexity

For the time space complexity of the three BST methods that we walked through (insert, search, and remove) we will be dealing with an average and worst case scenarios. In the average case, we will be dealing with a time complexity of O(log(n)) logarithmic time. Why? Because traversing starts at the root node of every BST after which we start our comparing logic and move down either the right or left branch of that root node. Whichever branch we move down on, we are essentially cutting the tree in half or rather completely disregarding the other subtree that is on the opposite branch that we did not travel to. So if our comparison logic leads us to the right branch of the root node then we can completely disregard the left sub tree of the root node because one we know that we are searching for a value that is higher than all the values in that left sub tree but moreso in general that is how searching in binary trees works. This method of “cutting in half” while searching through a BST equates to logarithmic time.

worst case for time complexity: O(n) linear time
time space complexity for a BST with iteration

Iteration vs Recursion

Why did I teach you how to build a basic BST with iteration? Because recursion can be difficult to understand from just reading. I believe that video materials are better suited towards guiding a programmer to understanding how and what recursion is doing. Here is a great video resource from freecodecamp constructing a basic BST with recurssion.

Conclusion

I want to thank you for making it all the way to the end of this article and I hope it was helpful. I intend on writing more posts like this going over data structures and algorithms, and your feedback is encouraged and appreciated. Happy coding and stay safe!

--

--

Get the Medium app

A button that says 'Download on the App Store', and if clicked it will lead you to the iOS App store
A button that says 'Get it on, Google Play', and if clicked it will lead you to the Google Play store