DEV Community

Cover image for Understanding Binary Search Trees

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...
Collapse
 
wulymammoth profile image
David • 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 :)

Collapse
 
christinamcmahon profile image
Christina

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!

Collapse
 
wulymammoth profile image
David

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:

1
  \ 
   2
     \
      3
        \
         4
           \
            5

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 :)

Thread Thread
 
christinamcmahon profile image
Christina

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 :)

Thread Thread
 
wulymammoth profile image
David

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

Collapse
 
aboub_g profile image
Abou Bakr G.

Great post! Thank you

Collapse
 
javierriveros profile image
Javier Riveros

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

Collapse
 
christinamcmahon profile image
Christina

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

Collapse
 
functional_js profile image
Functional Javascript

Great work Christina.

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

Source Code:

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

Collapse
 
christinamcmahon profile image
Christina

Thanks for sharing this!!

Collapse
 
functional_js profile image
Functional Javascript

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
        }
      }
    }
  };

Collapse
 
andrisgauracs profile image
Andris Gauračs

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