DEV Community

loading...

Discussion on: Understanding Binary Search Trees

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 Author

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

Forem Open with the Forem app