DEV Community

Understanding Binary Search Trees

Christina on July 17, 2020

As promised in my last post on recursion, which I recommend reading before this article as we will be using it a lot in my examples, I want to take...

Read full post

David • Jul 18 '20 • Edited

Good stuff, Christina...

I think that it may be worth mentioning, though, that data structures typically help us in some way -- rather than just being an exercise for some programming interviews. BSTs, of particular types are super useful and underpin some of the software that we use a lot. The "why" is not always answered and assumed/implicit.

That said, the worst-case scenario for search in standard binary trees (non-BSTs) is linear O(n). While in the average case a BST does it significantly faster (non-negligible), although the worst case is still O(n) in the scenario that we insert a sequential list of numbers, turning our BST into what would resemble a singly-linked list resulting in a linear scan O(n). I purposely omitted the time complexity for a BST in hopes that you'll go and discover it :)

Christina • Jul 20 '20

Thanks for your comment and the helpful info :) Correct me if I'm wrong but the time complexity of a BST is generally O(h) where h is the height of the BST. I thought about continuing this article by going over self-balancing trees but ran out of time last week so perhaps I'll write a future post about that since that can help our time complexity for the BST... Again, thanks for mentioning time complexity and the importance of data structures!

David • Jul 20 '20

You are correct -- O(h) and O(n) are the same here. Revisiting the example about inserting a sequence of numbers, let's say, [1, 2, 3, 4, 5] from left to right, will result in:

Now, imagine laying that flat.... 1 -> 2 -> 3 -> 4 -> 5. Linked list. Right? Worst-case search in a singly-linked list is linear - O(n). So in the context of trees, denoting runtime with n or h is okay so long as you and I and who we are communicating it to also understands what we are referencing :)

Yeah, self-balancing trees are such an interesting topic. If you asked me to implement it, probably can't off the top of my head. The rotations are non-trivial, but it's fun to know about the amazing benefits they provide -- guaranteeing performant runtimes by keeping the height as minimal as possible and not end up with the above example for very large data sets :)

I look forward to more! Keep up the awesome posts :)

Christina • Jul 20 '20

Thanks for that explanation, it helps! Talking with you has made me more excited to dive into this more so stay tuned because there's a good chance I'll post about self-balancing trees soon! Thanks for your support :)

David • Jul 22 '20

It'd be awesome! Your enthusiasm for this stuff is great, too! Looking forward to it!

Abou Bakr G. • Sep 9 '20

Great post! Thank you

Javier Riveros • Jul 18 '20

Great article, very easy to understand. Just to let you know there is a typo in the name of the method removeNode

Christina • Jul 20 '20

Glad you enjoyed it and thanks, I fixed the typo!

Functional Javascript • Jul 19 '20

Great work Christina.

I posted the full operational code if anyone's interested
bstClass.js

Source Code:

gist.github.com/funfunction/6a1b58...

Christina • Jul 20 '20

Thanks for sharing this!!

Functional Javascript • Jul 20 '20

No probs Christina.
I look forward to more goodies from you.

A note on the recursion idiom in Computer Science...

I am in the camp that recursion is a nasty antipattern.
I never use it my own code and never will.
Recursion can be reimplemented with a simple loop.
(I plan to write a post on this soon with a more indepth explanation)
The recursive insert() function blows up on my machine before 16,000 nodes.

Here is an example of the insert() recursive function, rewritten as an iterative function...
(Fun exercise: See if you can rewrite the rest of the recursive functions in this BSTClass ;-)

/**
  @method
  add a new node to the BST
  an implementation without recursion

  @pros vs recursion
  4 times faster in performance tests
  no stack overflow exception thrown (called a RangeError in JavaScript)
   - so no limit to BST node size
  a single method
  easier to grok

  @param {number} num - the data value of the node
  */
  insertIterativeNum(num) {
    const newNode = new Node(num);
    if (this.root === null) { //first base case
      this.root = newNode;
      return;
    }
    let t = this.root; //temporary node
    while (true) {
      if (newNode.data < t.data) {
        if (t.left === null) {
          t.left = newNode;
          break;
        } else {
          t = t.left;
        }
      } else {
        if (t.right === null) {
          t.right = newNode;
          break;
        } else {
          t = t.right
        }
      }
    }
  };

Andris Gauračs • Oct 8 '21

What is the function for this.minNode(node.right) ?