Search code examples
javascriptrecursiondata-structurestreebinary-tree

Recursion Stack Trace explanation using javascript


// Recursive javascript program for level
// order traversal of Binary Tree

// Class containing left and right child of current
// node and key value
class Node {
  constructor(val) {
    this.data = val;
    this.left = null;
    this.right = null;
  }
}


// Root of the Binary Tree
var root = null;

// Function to print level order traversal of tree
function printLevelOrder() {
  var h = height(root);
  var i;
  // for (i = 1; i <= h; i++)
  printCurrentLevel(root, h);
}

// Compute the "height" of a tree -- the number
// of nodes along the longest path
// from the root node down to the farthest leaf node.
function height(root) {
  if (root == null)
    return 0;
  else {
    // Compute height of each subtree
    var lheight = height(root.left);
    var rheight = height(root.right);

    // Use the larger one
    if (lheight > rheight)
      return (lheight + 1);
    else
      return (rheight + 1);
  }
}

// Print nodes at the current level
function printCurrentLevel(root, level) {

  //  alert("root data = "+root.data+" : level = "+level);


  document.getElementById("demo").innerHTML = document.getElementById("demo").innerHTML + "<br/>" + "root data = " + root.data + " : level = " + level + "";



  if (root == null)
    return;
  if (level == 1) {
    //alert(root.data);

  } else if (level > 1) {

    printCurrentLevel(root.left, level - 1);
    printCurrentLevel(root.right, level - 1);
  }
}

// Driver program to test above functions

root = new Node(1);
root.left = new Node(2);
root.right = new Node(3);
root.left.left = new Node(4);
root.left.right = new Node(5);
root.right.left = new Node(6);
root.right.right = new Node(7);

root.left.left.left = new Node(8);
root.left.left.right = new Node(9);



console.log("Level order traversal of  binary tree is ");
printLevelOrder();
<!DOCTYPE html>
<html>

<body>

  <h2>My First JavaScript</h2>


  <p id="demo"></p>

</body>

</html>

Why is the output for the above code is

root data = 1 : level = 4
root data = 2 : level = 3
root data = 4 : level = 2
root data = 8 : level = 1
root data = 9 : level = 1
root data = 5 : level = 2

it did not print root data = 3: level = 3 while using recursion

and if comment the code as below the output would be root data = 1 : level = 4

if (root == null)
       //   return ;

Please help me to understand this.

Reference: https://www.geeksforgeeks.org/level-order-tree-traversal/


Solution

  • The reason that node 3 is not printed is because program runs into an error before getting there.

    In this code:

      document.getElementById("demo").innerHTML = document.getElementById("demo").innerHTML + "<br/>" 
                                      + "root data = " + root.data + " : level = " + level + "";
      if (root == null)
        return;
    

    ...the first statement makes access to root.data, but it hasn't checked whether root might be null. That check comes too late. You shouldn't print anything when root happens to be null. So move the if guard before the "printing":

      if (root == null)
        return;
      document.getElementById("demo").innerHTML = document.getElementById("demo").innerHTML + "<br/>" 
                                      + "root data = " + root.data + " : level = " + level + "";
    

    Now the output will be:

    root data = 1 : level = 4
    root data = 2 : level = 3
    root data = 4 : level = 2
    root data = 8 : level = 1
    root data = 9 : level = 1
    root data = 5 : level = 2
    root data = 3 : level = 3
    root data = 6 : level = 2
    root data = 7 : level = 2
    

    Remarks

    • Although you refer to "level order traversal", this is not a level order traversal. In a level order traversal, you would need to get the output in this order:

      1 2 3 4 5 6 7 8 9
      

      Instead, your code has produced a pre-order traversal. Recursion is not the right mechanism for achieving a level-order traversal.

    • Level numbering is not as you have used it. Wikipedia states: "The level of a node is the number of edges along the unique path between it and the root node. This is the same as depth." That means the root should not get level number 4, but number 0. And deeper nodes will have a greater level number, not less.

    • The function printCurrentLevel doesn't really do what its name suggest: it prints all levels. It surely stops recurring when level is 1, but that would have happened anyway, because as you have numbered the levels, a node at level 1 has no children, so any recursive call would be made with root equal to null.

    • Following the previous point, you shouldn't need to calculate the height of the tree to make a traversal.

    • Even if you would use the concept of height, its common definition is the number of *edges from root to the deepest leaf, so that means your height is one unit off: a leaf node has height 0, and so for root == null you should return -1.

    Level order

    To implement level order, you typically use a queue instead of a stack, and so recursion is not the way to go.

    Here is an implementation of a level order traversal, outputting to the console. It uses a generator function, which is quite suitable for this purpose:

    class Node {
      constructor(val) {
        this.data = val;
        this.left = null;
        this.right = null;
      }
    }
    
    // Generator function for level order traversal of tree
    function* generateLevelOrder(root) {
        const queue = [root];
        for (const node of queue) {
            if (!node) continue;
            yield node.data;
            queue.push(node.left, node.right);
        }
    }
    
    // Driver program to test above functions
    
    var root = new Node(1);
    root.left = new Node(2);
    root.right = new Node(3);
    root.left.left = new Node(4);
    root.left.right = new Node(5);
    root.right.left = new Node(6);
    root.right.right = new Node(7);
    root.left.left.left = new Node(8);
    root.left.left.right = new Node(9);
    
    // Print level order:
    for (const data of generateLevelOrder(root)) {
        console.log(data);
    }