JavaScript Program to Check if all Leaf Nodes are at Same Level or Not
Given a binary tree our task is to check if all leaf nodes are at the same level. In a binary tree, all leaf nodes at the same level mean that every path from the root node to a leaf node has the same length.
Examples:
Binary tree:
1
/ \
2 3
/ \
4 5
/
6
Output: All leaf nodes are not at same level.
Below are the two approaches to check if all leaf nodes are at the same level:
Table of Content
- Level Order Traversal
- Recursive Approach
Level Order Traversal
In this approach, we traverse the binary tree level by level, starting from the root node. And we keep track of the level of each leaf node encountered. If at any point we encounter a leaf node at a level different from the ones we have seen before means all leaf nodes are not at same level so we return false. If we complete the traversal without finding any leaf node at a different level we return true.
Example: Implementation to check if all leaf nodes are at same level or not using level order traversal.
class TreeNode {
constructor(value) {
this.value = value;
this.left = null;
this.right = null;
}
}
function checkLevel(root) {
if (!root) return true;
let leafLevel = -1;
let queue = [{ node: root, level: 0 }];
while (queue.length > 0) {
let { node, level } = queue.shift();
if (!node.left && !node.right) {
if (leafLevel === -1) {
leafLevel = level;
} else if (leafLevel !== level) {
return false;
}
}
if (node.left)
queue.push({ node: node.left,
level: level + 1 });
if (node.right)
queue.push({ node: node.right,
level: level + 1 });
}
return true;
}
let root = new TreeNode(1);
root.left = new TreeNode(2);
root.right = new TreeNode(3);
root.left.left = new TreeNode(4);
root.left.right = new TreeNode(5);
root.left.right.left = new TreeNode(6);
if (checkLevel(root)) {
console.log("All leaf nodes are at same level.");
}
else {
console.log("All leaf nodes are not at same level.");
}
Output
All leaf nodes are not at same level.
Time Complexity: O(n)
Space Complexity: O(n)
Recursive Approach
In this approach we use a recursive function to traverse the binary tree. As we traverse the tree if we encounter a leaf node we compare its level with the previous leaf level. If the levels are different, we return false, Otherwise we continue the traversal. If the traversal completes without difference in levels of leaf nodes we return true.
Example: Implementation to check if all leaf nodes are at same level or not using recursive approach.
class TreeNode {
constructor(value) {
this.value = value;
this.left = null;
this.right = null;
}
}
function checkLevel(node, level = 0, leafLevel = -1) {
if (!node) return true;
if (!node.left && !node.right) {
if (leafLevel === -1) {
leafLevel = level;
} else if (leafLevel !== level) {
return false;
}
}
return checkLevel(node.left, level + 1, leafLevel)
&& checkLevel(node.right, level + 1, leafLevel);
}
let root = new TreeNode(5);
root.left = new TreeNode(3);
root.left.left = new TreeNode(1);
root.right = new TreeNode(9);
root.right.left = new TreeNode(2);
root.right.right = new TreeNode(4);
if (checkLevel(root)) {
console.log("All leaf nodes are at same level.");
}
else {
console.log("All leaf nodes are not at same level.");
}
Output
All leaf nodes are at same level.
Time Complexity: O(n)
Space Complexity: O(h)
Contact Us