// 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/
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
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.
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);
}