💡 Problem Formulation: In binary tree data structures, it is sometimes crucial to ascertain whether all leaf nodes reside at the same depth. This condition is important for certain applications such as balanced trees which affect algorithmic performance. We aim to check if all leaves of a binary tree end at the same level. The input will be a binary tree, and the desired output is a boolean value indicating whether all leaves are at the same depth.
Method 1: Recursion with Depth Tracking
This method involves a recursive traversal of the binary tree where the depth of the tree is passed down the recursion. We will use a helper function to check leaf node levels and compare them for equality.
Here’s an example:
class TreeNode:
def __init__(self, value=0, left=None, right=None):
self.val = value
self.left = left
self.right = right
def is_same_level(root):
depths = []
def check(node, depth):
if not node:
return True
if not node.left and not node.right: # It's a leaf node
if depth not in depths:
depths.append(depth)
return len(depths) == 1
return check(node.left, depth + 1) and check(node.right, depth + 1)
return check(root, 0)
# Example usage:
root = TreeNode(1, TreeNode(2), TreeNode(3, TreeNode(4), TreeNode(5)))
print(is_same_level(root))
The output of this code snippet would be:
False
This code snippet defines a binary tree and utilizes a recursive function check() to determine if all leaf nodes are at the same depth. The helper function traverses the tree, keeping track of the depth for each leaf node found and storing unique depths in a list. The function returns True if there is only one unique depth, False otherwise.
Method 2: Level Order Traversal
Level order traversal uses a queue to traverse the tree breadth-first. We track the depth of nodes and confirm if all leaves encountered are on the same level.
Here’s an example:
from collections import deque
def check_leaves_level(root):
if not root: return True
queue = deque([(root, 0)])
leaf_level = None
while queue:
node, level = queue.popleft()
if node.left:
queue.append((node.left, level + 1))
if node.right:
queue.append((node.right, level + 1))
if not node.left and not node.right: # It's a leaf node
if leaf_level is None:
leaf_level = level
elif level != leaf_level:
return False
return True
# Example usage:
root = TreeNode(1, TreeNode(2), TreeNode(3, TreeNode(4), TreeNode(5)))
print(check_leaves_level(root))
The output of this code snippet would be:
False
In this snippet, the function check_leaves_level() implements a breadth-first search utilizing a queue. It ensures that all leaf nodes visited are at the same level by setting a reference level for the first leaf and comparing subsequent leaves to this reference.
Method 3: Depth-First Search with Sentinel
Perform a depth-first search (DFS) but with a sentinel value which is updated only when the first leaf node is encountered. Further leaf nodes are compared against this sentinel.
Here’s an example:
def check_all_leaves_level_dfs(root):
leaf_level = [-1]
def dfs(node, level):
if not node:
return True
if not node.left and not node.right:
if leaf_level[0] == -1:
leaf_level[0] = level
return level == leaf_level[0]
return dfs(node.left, level + 1) and dfs(node.right, level + 1)
return dfs(root, 0)
# Example usage:
root = TreeNode(1, TreeNode(2), TreeNode(3, TreeNode(4), TreeNode(5)))
print(check_all_leaves_level_dfs(root))
The output of this code snippet would be:
False
This code defines a depth-first search function dfs() which verifies the level of each leaf. The leaf level is stored as a list leaf_level allowing us to modify the sentinel within the recursive function.
Method 4: Iterative DFS Using Stack
Iterative depth-first search mirrors recursion but leverages a stack. As the stack unwinds, we monitor the level of leaves and compare them to ensure they are on the same level.
Here’s an example:
def same_leaf_level(root):
if not root:
return True
stack = [(root, 0)]
leaf_level = None
while stack:
node, level = stack.pop()
if not node.left and not node.right: # A leaf node
if leaf_level is None:
leaf_level = level
elif leaf_level != level:
return False
if node.right:
stack.append((node.right, level + 1))
if node.left:
stack.append((node.left, level + 1))
return True
# Example usage:
root = TreeNode(1, TreeNode(2), TreeNode(3, TreeNode(4), TreeNode(5)))
print(same_leaf_level(root))
The output of this code snippet would be:
False
This code example uses an iterative DFS approach with a stack to track the nodes and levels. When a leaf node is encountered, the level is compared with an initially undefined leaf_level variable, making sure all leaves are at the same level.
Bonus One-Liner Method 5: Recursive Lambda with Global Variable
A compact one-liner using a recursive lambda function that utilizes a global variable to store the leaf level. A bit unconventional, but short and showcases the power of Python’s lambda functions and scope rules.
Here’s an example:
leaf_level = [None] is_same_level = lambda node, level=0: not node or (not node.left and not node.right and (leaf_level[0] == level if leaf_level[0] is not None else leaf_level.__setitem__(0, level))) or (is_same_level(node.left, level + 1) and is_same_level(node.right, level + 1)) # Example usage: root = TreeNode(1, TreeNode(2), TreeNode(3, TreeNode(4), TreeNode(5))) print(is_same_level(root))
The output of this code snippet would be:
False
This function is a one-liner lambda that determines if all the leaf nodes are at the same level. It is a compact representation of the previous methods, where a global list leaf_level tracks the depth of the first found leaf.
Summary/Discussion
- Method 1: Recursive Depth Tracking. Strength: Intuitive recursion accurately keeps track of depth. Weakness: Additional space for depth list and potentially deep recursion stack.
- Method 2: Level Order Traversal. Strength: Breadth-first search ensures level-by-level analysis. Weakness: Requires extra space for the queue, might not be as efficient.
- Method 3: DFS with Sentinel. Strength: Uses a sentinel for constant-time leaf level comparison. Weakness: Slight overhead for sentinel manipulation in a list.
- Method 4: Iterative DFS Using Stack. Strength: Simulates recursion without using call stack space. Weakness: Management of stack can be tricky.
- Method 5: One-Liner Lambda with Global. Strength: Elegant one-liner showcasing Python features. Weakness: Less readable and global variable usage not considered best practice.