Binary Trees - Complete Placement Interview Question Bank

Last Updated: March 2026

---

Introduction: Why Binary Trees Matter in Coding Interviews

Binary Trees are the cornerstone of recursive thinking and appear in 35-40% of technical interviews at top tech companies. They test your ability to:

• Think recursively and iteratively
• Understand tree traversals deeply
• Apply divide-and-conquer strategies
• Handle complex pointer manipulations

Binary trees are fundamental to:

• Database indexing (B-Trees)
• File systems (directory structures)
• Expression parsing (ASTs)
• Machine learning (decision trees)

Companies like Google, Amazon, Microsoft, and Meta frequently use tree problems to assess a candidate's problem-solving depth.

---

Key Concepts and Theory

1. Binary Tree Types

BINARY TREE (General):
        1
       / \
      2   3
     / \   \
    4   5   6

BINARY SEARCH TREE (BST):
        5
       / \
      3   8
     / \   \
    1   4   9
    
BALANCED BST (AVL/Red-Black):
        4
       / \
      2   6
     / \  / \
    1  3 5  7

COMPLETE BINARY TREE:
        1
       / \
      2   3
     / \  /
    4  5 6

2. Node Structure

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

3. Tree Properties

Property	Formula
Maximum nodes at level L	2^L
Maximum nodes in tree of height H	2^(H+1) - 1
Minimum height for N nodes	⌈log₂(N+1)⌉ - 1
Leaves in full binary tree	(Internal nodes) + 1
Total nodes in full binary tree	2 × Leaves - 1

---

Time/Space Complexity Cheat Sheet

┌─────────────────────────────────────────────────────────────┐
│ BINARY TREE OPERATIONS (N = nodes, H = height)              │
├─────────────────────────────────────────────────────────────┤
│ Traversal (any)      │ O(N)    │ Visit every node           │
│ Search (BST)         │ O(H)    │ O(log N) balanced          │
│ Insert (BST)         │ O(H)    │ O(log N) balanced          │
│ Delete (BST)         │ O(H)    │ O(log N) balanced          │
│ Find height          │ O(N)    │ Post-order traversal       │
│ Check balanced       │ O(N)    │ Bottom-up height check     │
│ Find diameter        │ O(N)    │ Modified height calculation│
│ Lowest Common Ancestor│ O(H)   │ Path comparison or recursive│
│ Serialize/Deserialize│ O(N)    │ Any traversal + reconstruction│
└─────────────────────────────────────────────────────────────┘

Space Complexities

Algorithm	Space
Recursive DFS	O(H) stack space
Iterative DFS	O(H) explicit stack
BFS	O(W) where W = max width
Morris Traversal	O(1)

---

Tree Traversals

Depth-First Search (DFS)

# Preorder: Root → Left → Right
def preorder(root):
    if not root:
        return
    print(root.val)      # Process root
    preorder(root.left)  # Process left
    preorder(root.right) # Process right

# Inorder: Left → Root → Right (gives sorted order for BST)
def inorder(root):
    if not root:
        return
    inorder(root.left)   # Process left
    print(root.val)      # Process root
    inorder(root.right)  # Process right

# Postorder: Left → Right → Root
def postorder(root):
    if not root:
        return
    postorder(root.left)  # Process left
    postorder(root.right) # Process right
    print(root.val)       # Process root

Breadth-First Search (BFS) - Level Order

from collections import deque

def level_order(root):
    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

---

Practice Questions with Solutions

Question 1: Maximum Depth of Binary Tree (EASY ⭐)

Problem: Find maximum depth (number of nodes along longest path from root to leaf).

Solution:

def max_depth(root):
    """
    Recursive - O(n) time, O(h) space
    """
    if not root:
        return 0
    
    left_depth = max_depth(root.left)
    right_depth = max_depth(root.right)
    
    return 1 + max(left_depth, right_depth)

# Iterative BFS
def max_depth_bfs(root):
    if not root:
        return 0
    
    from collections import deque
    queue = deque([root])
    depth = 0
    
    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

# Iterative DFS with stack
def max_depth_dfs(root):
    if not root:
        return 0
    
    stack = [(root, 1)]
    max_d = 0
    
    while stack:
        node, depth = stack.pop()
        max_d = max(max_d, depth)
        
        if node.left:
            stack.append((node.left, depth + 1))
        if node.right:
            stack.append((node.right, depth + 1))
    
    return max_d

---

Question 2: Same Tree (EASY ⭐)

Problem: Check if two binary trees are identical.

Solution:

def is_same_tree(p, q):
    """
    Recursive - O(n) time, O(h) space
    """
    # Both empty
    if not p and not q:
        return True
    
    # One empty, one not
    if not p or not q:
        return False
    
    # Values different
    if p.val != q.val:
        return False
    
    # Check subtrees
    return is_same_tree(p.left, q.left) and is_same_tree(p.right, q.right)

# Iterative
def is_same_tree_iterative(p, q):
    from collections import deque
    queue = deque([(p, q)])
    
    while queue:
        node1, node2 = queue.popleft()
        
        if not node1 and not node2:
            continue
        if not node1 or not node2:
            return False
        if node1.val != node2.val:
            return False
        
        queue.append((node1.left, node2.left))
        queue.append((node1.right, node2.right))
    
    return True

---

Question 3: Invert Binary Tree (EASY ⭐)

Problem: Mirror the binary tree (swap left and right children).

Solution:

def invert_tree(root):
    """
    Recursive - O(n) time, O(h) space
    """
    if not root:
        return None
    
    # Swap children
    root.left, root.right = root.right, root.left
    
    # Recursively invert subtrees
    invert_tree(root.left)
    invert_tree(root.right)
    
    return root

# Iterative BFS
def invert_tree_bfs(root):
    if not root:
        return None
    
    from collections import deque
    queue = deque([root])
    
    while queue:
        node = queue.popleft()
        
        # Swap
        node.left, node.right = node.right, node.left
        
        if node.left:
            queue.append(node.left)
        if node.right:
            queue.append(node.right)
    
    return root

---

Question 4: Binary Tree Level Order Traversal (MEDIUM ⭐⭐)

Problem: Return level order traversal as list of lists.

Solution:

from collections import deque

def level_order(root):
    """
    BFS - O(n) time, O(w) space where w = maximum width
    """
    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

# DFS approach (less intuitive but good to know)
def level_order_dfs(root):
    result = []
    
    def dfs(node, level):
        if not node:
            return
        
        # Ensure result has enough lists
        if level >= len(result):
            result.append([])
        
        result[level].append(node.val)
        dfs(node.left, level + 1)
        dfs(node.right, level + 1)
    
    dfs(root, 0)
    return result

---

Question 5: Validate Binary Search Tree (MEDIUM ⭐⭐)

Problem: Determine if binary tree is a valid BST.

Solution:

def is_valid_bst(root):
    """
    Recursive with min/max bounds - O(n) time, O(h) space
    
    Key: Every node must be within valid range
    """
    def validate(node, min_val, max_val):
        if not node:
            return True
        
        # Current node must be within bounds
        if node.val <= min_val or node.val >= max_val:
            return False
        
        # Left subtree: all values < node.val
        # Right subtree: all values > node.val
        return (validate(node.left, min_val, node.val) and
                validate(node.right, node.val, max_val))
    
    return validate(root, float('-inf'), float('inf'))

# Inorder traversal approach
def is_valid_bst_inorder(root):
    """
    Inorder of BST should be sorted - O(n) time, O(h) space
    """
    prev = [None]
    
    def inorder(node):
        if not node:
            return True
        
        if not inorder(node.left):
            return False
        
        # Check current
        if prev[0] is not None and node.val <= prev[0]:
            return False
        prev[0] = node.val
        
        return inorder(node.right)
    
    return inorder(root)

# Iterative inorder
def is_valid_bst_iterative(root):
    if not root:
        return True
    
    stack = []
    prev = None
    current = root
    
    while stack or current:
        # Go to leftmost
        while current:
            stack.append(current)
            current = current.left
        
        current = stack.pop()
        
        if prev is not None and current.val <= prev:
            return False
        
        prev = current.val
        current = current.right
    
    return True

---

Question 6: Lowest Common Ancestor of BST (EASY ⭐)

Problem: Find LCA of two nodes in a BST.

Solution:

def lowest_common_ancestor(root, p, q):
    """
    Utilize BST property - O(h) time, O(1) space
    
    Key: LCA is where paths to p and q diverge
    """
    while root:
        # Both nodes in right subtree
        if p.val > root.val and q.val > root.val:
            root = root.right
        # Both nodes in left subtree
        elif p.val < root.val and q.val < root.val:
            root = root.left
        else:
            # Nodes are on different sides (or one is root)
            return root
    
    return None

# Recursive
def lowest_common_ancestor_recursive(root, p, q):
    if not root:
        return None
    
    # Both in right subtree
    if p.val > root.val and q.val > root.val:
        return lowest_common_ancestor_recursive(root.right, p, q)
    
    # Both in left subtree
    if p.val < root.val and q.val < root.val:
        return lowest_common_ancestor_recursive(root.left, p, q)
    
    # Divergence point found
    return root

---

Question 7: Lowest Common Ancestor of Binary Tree (MEDIUM ⭐⭐)

Problem: Find LCA in a general binary tree (not BST).

Solution:

def lowest_common_ancestor_bt(root, p, q):
    """
    Recursive - O(n) time, O(h) space
    
    Returns:
    - p if p is found (q might be in subtree)
    - q if q is found (p might be in subtree)
    - LCA if both found
    - None if neither found
    """
    if not root or root == p or root == q:
        return root
    
    left = lowest_common_ancestor_bt(root.left, p, q)
    right = lowest_common_ancestor_bt(root.right, p, q)
    
    # Both found in different subtrees
    if left and right:
        return root
    
    # Both in left or right, or not found
    return left if left else right

---

Question 8: Binary Tree Right Side View (MEDIUM ⭐⭐)

Problem: Given root, return values visible from right side.

Solution:

from collections import deque

def right_side_view(root):
    """
    BFS - O(n) time, O(w) space
    """
    if not root:
        return []
    
    result = []
    queue = deque([root])
    
    while queue:
        level_size = len(queue)
        
        for i in range(level_size):
            node = queue.popleft()
            
            # Last node in level is visible from right
            if i == level_size - 1:
                result.append(node.val)
            
            if node.left:
                queue.append(node.left)
            if node.right:
                queue.append(node.right)
    
    return result

# DFS (preorder, prioritize right)
def right_side_view_dfs(root):
    result = []
    
    def dfs(node, level):
        if not node:
            return
        
        # First time at this level, record node
        if level == len(result):
            result.append(node.val)
        
        # Go right first
        dfs(node.right, level + 1)
        dfs(node.left, level + 1)
    
    dfs(root, 0)
    return result

---

Question 9: Construct Binary Tree from Preorder and Inorder (MEDIUM ⭐⭐)

Problem: Build tree from preorder and inorder traversals.

Solution:

def build_tree(preorder, inorder):
    """
    Recursive - O(n) time with hash map, O(h) space
    
    Key insight:
    - Preorder: Root → Left → Right (root is first)
    - Inorder: Left → Root → Right (root splits L and R)
    """
    # Build value to index map for inorder
    inorder_map = {val: idx for idx, val in enumerate(inorder)}
    
    def construct(pre_start, pre_end, in_start, in_end):
        if pre_start > pre_end or in_start > in_end:
            return None
        
        # Root is first in preorder
        root_val = preorder[pre_start]
        root = TreeNode(root_val)
        
        # Find root position in inorder
        in_root_idx = inorder_map[root_val]
        
        # Calculate left subtree size
        left_size = in_root_idx - in_start
        
        # Build left subtree
        root.left = construct(
            pre_start + 1,
            pre_start + left_size,
            in_start,
            in_root_idx - 1
        )
        
        # Build right subtree
        root.right = construct(
            pre_start + left_size + 1,
            pre_end,
            in_root_idx + 1,
            in_end
        )
        
        return root
    
    return construct(0, len(preorder) - 1, 0, len(inorder) - 1)

---

Question 10: Path Sum (EASY ⭐)

Problem: Determine if root-to-leaf path sums to target.

Solution:

def has_path_sum(root, target_sum):
    """
    Recursive DFS - O(n) time, O(h) space
    """
    if not root:
        return False
    
    # Leaf node check
    if not root.left and not root.right:
        return root.val == target_sum
    
    # Check subtrees with reduced sum
    remaining = target_sum - root.val
    return has_path_sum(root.left, remaining) or has_path_sum(root.right, remaining)

# Iterative
def has_path_sum_iterative(root, target_sum):
    if not root:
        return False
    
    stack = [(root, target_sum - root.val)]
    
    while stack:
        node, current_sum = stack.pop()
        
        if not node.left and not node.right and current_sum == 0:
            return True
        
        if node.right:
            stack.append((node.right, current_sum - node.right.val))
        if node.left:
            stack.append((node.left, current_sum - node.left.val))
    
    return False

---

Question 11: Path Sum II (MEDIUM ⭐⭐)

Problem: Find all root-to-leaf paths that sum to target.

Solution:

def path_sum(root, target_sum):
    """
    Backtracking DFS - O(n) time, O(h) space for recursion + O(n) for paths
    """
    result = []
    
    def dfs(node, remaining, path):
        if not node:
            return
        
        path.append(node.val)
        
        # Leaf check
        if not node.left and not node.right and node.val == remaining:
            result.append(path[:])  # Copy path
        
        # Explore subtrees
        dfs(node.left, remaining - node.val, path)
        dfs(node.right, remaining - node.val, path)
        
        path.pop()  # Backtrack
    
    dfs(root, target_sum, [])
    return result

---

Question 12: Binary Tree Maximum Path Sum (HARD ⭐⭐⭐)

Problem: Find maximum path sum (any path, not necessarily root-to-leaf).

Solution:

def max_path_sum(root):
    """
    Post-order DFS - O(n) time, O(h) space
    
    For each node, calculate:
    1. Max path through node as "arch" (left + node + right)
    2. Max path ending at node (can extend to parent)
    """
    max_sum = [float('-inf')]
    
    def max_gain(node):
        if not node:
            return 0
        
        # Max gain from left and right (ignore negative)
        left_gain = max(max_gain(node.left), 0)
        right_gain = max(max_gain(node.right), 0)
        
        # Price of path going through node
        price_new_path = node.val + left_gain + right_gain
        
        # Update global max
        max_sum[0] = max(max_sum[0], price_new_path)
        
        # Return max gain if continue same path
        return node.val + max(left_gain, right_gain)
    
    max_gain(root)
    return max_sum[0]

---

Question 13: Serialize and Deserialize Binary Tree (HARD ⭐⭐⭐)

Problem: Design algorithm to serialize/deserialize tree to string.

Solution:

class Codec:
    """
    Preorder with null markers - O(n) time, O(n) space
    """
    def serialize(self, root):
        """Encodes tree to single string"""
        def helper(node):
            if not node:
                result.append('#')
                return
            result.append(str(node.val))
            helper(node.left)
            helper(node.right)
        
        result = []
        helper(root)
        return ','.join(result)
    
    def deserialize(self, data):
        """Decodes string to tree"""
        def helper():
            val = next(values)
            if val == '#':
                return None
            node = TreeNode(int(val))
            node.left = helper()
            node.right = helper()
            return node
        
        values = iter(data.split(','))
        return helper()

# Level order (BFS) approach
class CodecBFS:
    def serialize(self, root):
        if not root:
            return ''
        
        result = []
        queue = deque([root])
        
        while queue:
            node = queue.popleft()
            if node:
                result.append(str(node.val))
                queue.append(node.left)
                queue.append(node.right)
            else:
                result.append('#')
        
        return ','.join(result)
    
    def deserialize(self, data):
        if not data:
            return None
        
        values = data.split(',')
        root = TreeNode(int(values[0]))
        queue = deque([root])
        i = 1
        
        while queue:
            node = queue.popleft()
            
            # Left child
            if values[i] != '#':
                node.left = TreeNode(int(values[i]))
                queue.append(node.left)
            i += 1
            
            # Right child
            if values[i] != '#':
                node.right = TreeNode(int(values[i]))
                queue.append(node.right)
            i += 1
        
        return root

---

Question 14: Populating Next Right Pointers (MEDIUM ⭐⭐)

Problem: Populate each next pointer to point to its next right node.

Solution:

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

def connect(root):
    """
    Level-by-level linking - O(n) time, O(1) space
    """
    if not root:
        return None
    
    leftmost = root
    
    while leftmost.left:
        head = leftmost
        
        while head:
            # Connect children of same parent
            head.left.next = head.right
            
            # Connect to cousin's subtree
            if head.next:
                head.right.next = head.next.left
            
            head = head.next
        
        leftmost = leftmost.left
    
    return root

# BFS approach - O(n) time, O(w) space
def connect_bfs(root):
    if not root:
        return None
    
    from collections import deque
    queue = deque([root])
    
    while queue:
        level_size = len(queue)
        
        for i in range(level_size):
            node = queue.popleft()
            
            if i < level_size - 1:
                node.next = queue[0]
            
            if node.left:
                queue.append(node.left)
            if node.right:
                queue.append(node.right)
    
    return root

---

Question 15: Flatten Binary Tree to Linked List (MEDIUM ⭐⭐)

Problem: Flatten tree to linked list in-place (preorder).

Solution:

def flatten(root):
    """
    Recursive post-order - O(n) time, O(h) space
    """
    if not root:
        return None
    
    # Flatten subtrees
    flatten(root.left)
    flatten(root.right)
    
    # Save right subtree
    right_subtree = root.right
    
    # Move left to right
    root.right = root.left
    root.left = None
    
    # Find end of new right subtree
    current = root
    while current.right:
        current = current.right
    
    # Attach original right subtree
    current.right = right_subtree

# Morris traversal - O(n) time, O(1) space
def flatten_morris(root):
    current = root
    
    while current:
        if current.left:
            # Find rightmost node in left subtree
            rightmost = current.left
            while rightmost.right:
                rightmost = rightmost.right
            
            # Rewire
            rightmost.right = current.right
            current.right = current.left
            current.left = None
        
        current = current.right

---

Question 16: Diameter of Binary Tree (EASY ⭐)

Problem: Find length of longest path between any two nodes.

Solution:

def diameter_of_binary_tree(root):
    """
    Modified post-order - O(n) time, O(h) space
    
    Diameter at node = left_height + right_height
    """
    diameter = [0]
    
    def height(node):
        if not node:
            return 0
        
        left_h = height(node.left)
        right_h = height(node.right)
        
        # Update diameter (path through this node)
        diameter[0] = max(diameter[0], left_h + right_h)
        
        # Return height
        return 1 + max(left_h, right_h)
    
    height(root)
    return diameter[0]

---

Question 17: Kth Smallest Element in BST (MEDIUM ⭐⭐)

Problem: Find kth smallest element in BST.

Solution:

def kth_smallest(root, k):
    """
    Inorder traversal - O(h + k) time, O(h) space
    """
    stack = []
    current = root
    
    while True:
        # Go to leftmost
        while current:
            stack.append(current)
            current = current.left
        
        current = stack.pop()
        k -= 1
        
        if k == 0:
            return current.val
        
        current = current.right

# With parent pointers or augmentation, can do O(h)
class TreeNodeAugmented:
    def __init__(self, val=0):
        self.val = val
        self.left = None
        self.right = None
        self.count = 1  # Size of subtree

def kth_smallest_augmented(root, k):
    """O(h) with augmented tree"""
    left_count = root.left.count if root.left else 0
    
    if k <= left_count:
        return kth_smallest_augmented(root.left, k)
    elif k == left_count + 1:
        return root.val
    else:
        return kth_smallest_augmented(root.right, k - left_count - 1)

---

Question 18: Lowest Common Ancestor of Deepest Leaves (MEDIUM ⭐⭐)

Problem: Find LCA of all deepest leaves.

Solution:

def lca_deepest_leaves(root):
    """
    Post-order - O(n) time, O(h) space
    
    Returns (lca_node, depth)
    """
    def dfs(node):
        if not node:
            return (None, 0)
        
        left_lca, left_depth = dfs(node.left)
        right_lca, right_depth = dfs(node.right)
        
        if left_depth > right_depth:
            return (left_lca, left_depth + 1)
        elif right_depth > left_depth:
            return (right_lca, right_depth + 1)
        else:
            # Deepest leaves on both sides, current is LCA
            return (node, left_depth + 1)
    
    return dfs(root)[0]

---

Question 19: Count Complete Tree Nodes (MEDIUM ⭐⭐)

Problem: Count nodes in complete binary tree faster than O(n).

Solution:

def count_nodes(root):
    """
    O((log n)²) by comparing left and right heights
    """
    if not root:
        return 0
    
    # Get left height (follow left edges)
    left_height = 0
    node = root
    while node:
        left_height += 1
        node = node.left
    
    # Get right height (follow right edges)
    right_height = 0
    node = root
    while node:
        right_height += 1
        node = node.right
    
    # Perfect binary tree
    if left_height == right_height:
        return (1 << left_height) - 1  # 2^h - 1
    
    # Not perfect, count recursively
    return 1 + count_nodes(root.left) + count_nodes(root.right)

---

Question 20: Vertical Order Traversal (HARD ⭐⭐⭐)

Problem: Return vertical order traversal (column by column, top to bottom).

Solution:

from collections import defaultdict, deque

def vertical_traversal(root):
    """
    BFS with column tracking - O(n log n) time, O(n) space
    """
    if not root:
        return []
    
    # column -> list of (row, value)
    column_table = defaultdict(list)
    
    queue = deque([(root, 0, 0)])  # (node, column, row)
    
    while queue:
        node, col, row = queue.popleft()
        
        column_table[col].append((row, node.val))
        
        if node.left:
            queue.append((node.left, col - 1, row + 1))
        if node.right:
            queue.append((node.right, col + 1, row + 1))
    
    result = []
    for col in sorted(column_table.keys()):
        # Sort by row, then by value
        column_table[col].sort()
        result.append([val for row, val in column_table[col]])
    
    return result

---

Common Interview Follow-up Questions

1. "Can you do this iteratively?"

   • Know both recursive and iterative approaches
   • Iterative often uses explicit stack/queue

2. "What if the tree is extremely unbalanced?"

   • Time complexity becomes O(n) instead of O(log n)
   • Consider self-balancing trees (AVL, Red-Black)

3. "How would you parallelize this?"

   • Independent subtrees can be processed concurrently
   • Thread pools for different branches

4. "What about N-ary trees?"

   • Similar principles apply
   • Children stored in list instead of left/right

5. "Memory optimization for very large trees?"

   • Morris traversal for O(1) space
   • Streaming processing without building tree

---

Companies That Frequently Ask Trees

Company	Frequency	Common Questions
Google	⭐⭐⭐⭐⭐	Serialize/Deserialize, Max Path Sum, LCA
Amazon	⭐⭐⭐⭐⭐	Level Order, Validate BST, Path Sum
Microsoft	⭐⭐⭐⭐	Invert Tree, Build from Traversals, Diameter
Meta	⭐⭐⭐⭐	Right Side View, Connect Next, Flatten
Apple	⭐⭐⭐⭐	Same Tree, Symmetric Tree, Max Depth
Netflix	⭐⭐⭐	Vertical Order, Boundary Traversal
Uber	⭐⭐⭐	Kth Smallest, BST Iterator, Closest Value
Adobe	⭐⭐⭐	Path Sum variations, Sum Root to Leaf

---

Preparation Tips for Tree Problems

1. Master All Traversals: Know when to use pre, in, post-order. Inorder gives sorted BST.

2. Recognize Patterns:

   • Path problems → Backtracking DFS
   • Level problems → BFS
   • Construction problems → Divide and conquer with traversals

3. Practice Tree Construction: Building from traversals is common and tricky.

4. Handle Edge Cases: Empty tree, single node, skewed trees, duplicate values.

5. Space Optimization: Know Morris traversal for O(1) space inorder.

6. Augmented Trees: Understand how to maintain subtree information (size, sum).

7. Iterative Conversions: Practice converting recursive solutions to iterative.

---

Frequently Asked Questions (FAQ)

Q1: BFS vs DFS - which should I use?

A:

• BFS: Level-order problems, shortest path in unweighted tree, visible nodes
• DFS: Path problems, tree construction, problems requiring backtracking

Q2: How do I reconstruct a tree from traversals?

A:

• Preorder + Inorder: Preorder gives root, inorder splits L/R
• Postorder + Inorder: Similar, root is last in postorder
• Preorder + Postorder: Only works for full binary trees

Q3: What's the difference between height and depth?

A:

• Depth: Distance from root to node (root depth = 0)
• Height: Distance from node to deepest leaf (leaf height = 0)
• Tree height = max depth of any node

Q4: Can I solve tree problems without recursion?

A: Yes, using explicit stack (DFS) or queue (BFS). Recursion is cleaner but has O(h) stack overhead. Morris traversal achieves O(1) space for inorder.

Q5: How do I handle very large trees that don't fit in memory?

A:

• External memory algorithms
• Streaming processing
• Database storage with indexed access
• Lazy loading of subtrees

---

Quick Reference: Tree Patterns

┌────────────────────────────────────────────────────────────────┐
│ PATTERN             │ WHEN TO USE                              │
├────────────────────────────────────────────────────────────────┤
│ DFS (Recursive)     │ Path finding, tree construction          │
│ BFS (Level Order)   │ Shortest path, level-by-level processing │
│ Divide & Conquer    │ Building from traversals, large trees    │
│ Backtracking        │ All paths, path sum variations           │
│ Post-order          │ When you need info from both subtrees    │
│ In-order            │ BST validation, sorted order             │
│ Pre-order           │ Root processing before children          │
│ Morris Traversal    │ O(1) space inorder traversal             │
└────────────────────────────────────────────────────────────────┘

---

Grow your skills from the roots up! 🌳