DEV Community


Discussion on: Understanding Binary Search Trees

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

  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;
    let t = this.root; //temporary node
    while (true) {
      if ( < {
        if (t.left === null) {
          t.left = newNode;
        } else {
          t = t.left;
      } else {
        if (t.right === null) {
          t.right = newNode;
        } else {
          t = t.right

Forem Open with the Forem app