Ensuring Equal Leaf Levels: Python Approaches to Verify Leaf Node Depth in Binary Trees

πŸ’‘ 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.