Intermediate

Binary Tree Problems

Six fundamental binary tree problems with complete Python solutions. Traversals are the foundation for every tree algorithm — from parsing decision tree structures to walking computation graphs during backpropagation. Master these patterns and the rest of tree problems become variations.

Problem 1: Inorder Traversal

🎯

Problem: Given the root of a binary tree, return the inorder traversal of its nodes' values (left, root, right).
ML Context: Inorder traversal of a BST-based decision tree yields sorted feature thresholds, useful for understanding how the model partitions feature space.

class TreeNode:
    def __init__(self, val=0, left=None, right=None):
        self.val = val
        self.left = left
        self.right = right

def inorder_traversal(root: TreeNode) -> list:
    """Iterative inorder traversal using explicit stack.
    Time: O(n), Space: O(h) where h = tree height.
    """
    result = []
    stack = []
    current = root

    while current or stack:
        # Go as far left as possible
        while current:
            stack.append(current)
            current = current.left
        # Process node
        current = stack.pop()
        result.append(current.val)
        # Move to right subtree
        current = current.right

    return result

# Recursive version (cleaner but uses call stack)
def inorder_recursive(root: TreeNode) -> list:
    if not root:
        return []
    return inorder_recursive(root.left) + [root.val] + inorder_recursive(root.right)

# Test
#       1
#      / \
#     2   3
#    / \
#   4   5
root = TreeNode(1, TreeNode(2, TreeNode(4), TreeNode(5)), TreeNode(3))
print(inorder_traversal(root))    # [4, 2, 5, 1, 3]
print(inorder_recursive(root))    # [4, 2, 5, 1, 3]

Problem 2: Preorder and Postorder Traversals

🎯

Problem: Implement preorder (root, left, right) and postorder (left, right, root) traversals.
ML Context: Preorder traversal maps to how decision trees evaluate — check the root condition first, then recurse. Postorder maps to backpropagation — compute children's gradients before the parent's.

def preorder_traversal(root: TreeNode) -> list:
    """Iterative preorder: root -> left -> right.
    Time: O(n), Space: O(h).
    """
    if not root:
        return []
    result = []
    stack = [root]

    while stack:
        node = stack.pop()
        result.append(node.val)
        # Push right first so left is processed first (LIFO)
        if node.right:
            stack.append(node.right)
        if node.left:
            stack.append(node.left)

    return result

def postorder_traversal(root: TreeNode) -> list:
    """Iterative postorder: left -> right -> root.
    Trick: reverse of modified preorder (root -> right -> left).
    Time: O(n), Space: O(h).
    """
    if not root:
        return []
    result = []
    stack = [root]

    while stack:
        node = stack.pop()
        result.append(node.val)
        # Push left first, then right (opposite of preorder)
        if node.left:
            stack.append(node.left)
        if node.right:
            stack.append(node.right)

    return result[::-1]  # Reverse to get postorder

# Test
root = TreeNode(1, TreeNode(2, TreeNode(4), TreeNode(5)), TreeNode(3))
print(preorder_traversal(root))   # [1, 2, 4, 5, 3]
print(postorder_traversal(root))  # [4, 5, 2, 3, 1]

Problem 3: Level-Order Traversal (BFS)

🎯

Problem: Given the root of a binary tree, return the level-order traversal as a list of lists (each inner list = one level).
ML Context: Level-order traversal is how you inspect a decision tree layer by layer — first the root split, then the second-level splits, etc. Also used in beam search decoding for language models.

from collections import deque

def level_order(root: TreeNode) -> list:
    """BFS level-order traversal.
    Time: O(n), Space: O(w) where w = max width of tree.
    """
    if not root:
        return []

    result = []
    queue = deque([root])

    while queue:
        level_size = len(queue)
        level = []
        for _ in range(level_size):
            node = queue.popleft()
            level.append(node.val)
            if node.left:
                queue.append(node.left)
            if node.right:
                queue.append(node.right)
        result.append(level)

    return result

# Test
#       3
#      / \
#     9  20
#       /  \
#      15   7
root = TreeNode(3, TreeNode(9), TreeNode(20, TreeNode(15), TreeNode(7)))
print(level_order(root))  # [[3], [9, 20], [15, 7]]

Problem 4: Maximum Depth of Binary Tree

🎯

Problem: Given the root of a binary tree, return its maximum depth (number of nodes along the longest path from root to leaf).
ML Context: The depth of a decision tree directly controls model complexity. Deeper trees overfit; shallower trees underfit. max_depth is the most important hyperparameter in XGBoost and scikit-learn decision trees.

def max_depth(root: TreeNode) -> int:
    """Recursive DFS to find maximum depth.
    Time: O(n), Space: O(h).
    """
    if not root:
        return 0
    return 1 + max(max_depth(root.left), max_depth(root.right))

def max_depth_iterative(root: TreeNode) -> int:
    """BFS approach - count number of levels.
    Time: O(n), Space: O(w).
    """
    if not root:
        return 0
    depth = 0
    queue = deque([root])
    while queue:
        depth += 1
        for _ in range(len(queue)):
            node = queue.popleft()
            if node.left:
                queue.append(node.left)
            if node.right:
                queue.append(node.right)
    return depth

# Test
root = TreeNode(3, TreeNode(9), TreeNode(20, TreeNode(15), TreeNode(7)))
print(max_depth(root))            # 3
print(max_depth_iterative(root))  # 3

Problem 5: Symmetric Tree

🎯

Problem: Given the root of a binary tree, check whether it is a mirror of itself (symmetric around its center).
ML Context: Symmetry detection appears in image classification (data augmentation via horizontal flips) and in verifying balanced tree structures for efficient model storage.

def is_symmetric(root: TreeNode) -> bool:
    """Check if tree is symmetric using recursive mirror comparison.
    Time: O(n), Space: O(h).
    """
    def is_mirror(left: TreeNode, right: TreeNode) -> bool:
        if not left and not right:
            return True
        if not left or not right:
            return False
        return (left.val == right.val and
                is_mirror(left.left, right.right) and
                is_mirror(left.right, right.left))

    return is_mirror(root.left, root.right) if root else True

def is_symmetric_iterative(root: TreeNode) -> bool:
    """Iterative approach using queue.
    Time: O(n), Space: O(w).
    """
    if not root:
        return True
    queue = deque([(root.left, root.right)])
    while queue:
        left, right = queue.popleft()
        if not left and not right:
            continue
        if not left or not right:
            return False
        if left.val != right.val:
            return False
        queue.append((left.left, right.right))
        queue.append((left.right, right.left))
    return True

# Test
#       1
#      / \
#     2   2
#    / \ / \
#   3  4 4  3
root = TreeNode(1,
    TreeNode(2, TreeNode(3), TreeNode(4)),
    TreeNode(2, TreeNode(4), TreeNode(3))
)
print(is_symmetric(root))            # True
print(is_symmetric_iterative(root))  # True

Problem 6: Path Sum

🎯

Problem: Given the root of a binary tree and a target sum, return True if there exists a root-to-leaf path where the values sum to the target.
ML Context: In decision trees, each root-to-leaf path represents a classification rule. The "path sum" pattern mirrors how you trace which feature conditions led to a specific prediction — critical for model interpretability (SHAP tree explainer uses path tracing).

def has_path_sum(root: TreeNode, target_sum: int) -> bool:
    """Check if any root-to-leaf path sums to target.
    Time: O(n), Space: O(h).
    """
    if not root:
        return False
    # Leaf node check
    if not root.left and not root.right:
        return root.val == target_sum
    # Recurse with reduced target
    remaining = target_sum - root.val
    return (has_path_sum(root.left, remaining) or
            has_path_sum(root.right, remaining))

def all_path_sums(root: TreeNode, target_sum: int) -> list:
    """Return ALL root-to-leaf paths that sum to target.
    Time: O(n^2) worst case, Space: O(n * h).
    """
    result = []

    def dfs(node, remaining, path):
        if not node:
            return
        path.append(node.val)
        if not node.left and not node.right and remaining == node.val:
            result.append(list(path))  # Copy path
        dfs(node.left, remaining - node.val, path)
        dfs(node.right, remaining - node.val, path)
        path.pop()  # Backtrack

    dfs(root, target_sum, [])
    return result

# Test
#       5
#      / \
#     4   8
#    /   / \
#   11  13  4
#  / \       \
# 7   2       1
root = TreeNode(5,
    TreeNode(4, TreeNode(11, TreeNode(7), TreeNode(2))),
    TreeNode(8, TreeNode(13), TreeNode(4, None, TreeNode(1)))
)
print(has_path_sum(root, 22))       # True (5->4->11->2)
print(all_path_sums(root, 22))     # [[5, 4, 11, 2]]

Traversal Summary

Traversal	Order	Use Case	ML Application
Inorder	Left, Root, Right	Get sorted order from BST	Sorted feature thresholds in decision trees
Preorder	Root, Left, Right	Copy/serialize a tree	Decision tree evaluation (check root first)
Postorder	Left, Right, Root	Delete tree, evaluate expression	Backpropagation (children before parent)
Level-order	Level by level (BFS)	Print tree by depth	Beam search, layer-by-layer model inspection

💡

Interview pattern: Most binary tree problems boil down to choosing the right traversal. Ask yourself: (1) Do I need sorted order? Use inorder. (2) Do I need to process parent before children? Use preorder. (3) Do I need to process children before parent? Use postorder. (4) Do I need to process level by level? Use level-order (BFS).

← Previous Trees & Graphs in AI/ML Next → BST Problems