|
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:
Level Order TraversalIn 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.
JavaScript
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.");
}
OutputAll leaf nodes are not at same level.
Time Complexity: O(n)
Space Complexity: O(n)
Recursive ApproachIn 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.
JavaScript
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.");
}
OutputAll leaf nodes are at same level.
Time Complexity: O(n)
Space Complexity: O(h)
Depth-First Search (DFS) ApproachIn this approach, we use an iterative DFS to traverse the binary tree. We maintain a stack to keep track of nodes and their levels. As we encounter leaf nodes, we record their levels and ensure they are consistent.
Example: Implementation to check if all leaf nodes are at the same level or not using DFS
JavaScript
class TreeNode {
constructor(value) {
this.value = value;
this.left = null;
this.right = null;
}
}
function checkLevelDFS(root) {
if (!root) return true;
let stack = [{ node: root, level: 0 }];
let leafLevel = -1;
while (stack.length > 0) {
let { node, level } = stack.pop();
if (!node.left && !node.right) {
if (leafLevel === -1) {
leafLevel = level;
} else if (leafLevel !== level) {
return false;
}
}
if (node.right)
stack.push({ node: node.right, level: level + 1 });
if (node.left)
stack.push({ node: node.left, level: level + 1 });
}
return true;
}
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 (checkLevelDFS(root)) {
console.log("All leaf nodes are at same level.");
}
else {
console.log("All leaf nodes are not at same level.");
}
OutputAll leaf nodes are at same level.
Time Complexity: O(n)
Space Complexity: O(n)
|
