Discussion on: Understanding Binary Search Trees

View post

Replies for: Thanks for sharing this!!

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