Question 239400 in Javascript Question posted in
A very good W3school tutorial can be found here.

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/

Tags:

2

Answers


  1. 0

    The reason why the output does not include root data = 3 : level = 3 when using recursion is because of the way the printCurrentLevel function is implemented.

    In the printCurrentLevel function, you are checking the value of the level parameter to determine whether to print the current node’s data or to continue recursively on its children.

    However, when you reach the level where level == 1, you are correctly printing the data, but after that, the else if (level > 1) condition prevents further recursion, which is why the printCurrentLevel function doesn’t continue to the third level of the tree.

    To fix this: You should modify the printCurrentLevel function to remove the else if condition. Instead of stopping the recursion when level > 1, you should allow the recursion to continue regardless of the level value.

    Here’s how you can modify the function:

    function printCurrentLevel(root, level) {
  if (root == null)
    return;
  
  // Print the data at this level
  if (level == 1) {
    document.getElementById("demo").innerHTML +=
      "<br/>" + "root data = " + root.data + " : level = " + level + "";
  }

  // Recurse on left and right children
  printCurrentLevel(root.left, level - 1);
  printCurrentLevel(root.right, level - 1);
}

    With this change, the recursion will continue even when level > 1, and you should see the expected output including root data = 3 : level = 3 as well.

    Login or Signup to reply.
  2. 0

    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 1. 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) 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);
}
    Login or Signup to reply.
Please signup or login to give your own answer.

Back To Top
Search