7.1 Binary Trees (DFS, BFS & Bottom-Up Recursion)

1. What Is a Binary Tree?

Up until now, Arrays, Linked Lists, Stacks, and Queues were all 1D lines (each item had at most one next neighbor).

A Binary Tree is a hierarchical data structure (like a family tree or a folder directory on your computer):

• It starts at a single top node called the root.
• Every TreeNode holds a value (val) and up to two children: left and right.
• A node with no children (left == null and right == null) is called a leaf.
• Unlike a Graph, a Tree never has cycles — there is only one unique path from the root to any node!

2. Why Do We Need Binary Trees & How Do We Walk Them?

Why Trees Exist

Flat arrays cannot represent nested hierarchies (like HTML DOM elements, organization charts, or decision trees). Trees also divide data into two branches at every level, so a balanced tree of 1,000,000 nodes is only 20 levels tall (log2(1,000,000) ≈ 20)!

The Two Ways to Traverse Every Node (O(N) Time)

1. Depth-First Search (DFS — via Recursion): Plunge all the way down to a leaf before backing up.
   • Preorder (Root -> Left -> Right): Visit the parent before its children.
   • Inorder (Left -> Root -> Right): Visit left subtree, then parent, then right subtree.
   • Postorder (Left -> Right -> Root): Visit both children first, then combine their answers at the parent (Bottom-Up Recursion!).
2. Breadth-First Search (BFS — via a FIFO Queue): Visit the tree floor by floor (Level 0, then Level 1, then Level 2).

Comparison Table: Which Tree Traversal Should You Pick?

3. Basic Operations & Walkthroughs (All 4 Languages)

from collections import deque

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

# 1. Bottom-Up Postorder DFS: Max Depth (Height) of a Binary Tree -> O(N)
def max_depth(root: TreeNode) -> int:
  if not root:
      return 0
  left_h = max_depth(root.left)
  right_h = max_depth(root.right)
  return 1 + max(left_h, right_h)

# 2. Level-Order BFS (Floor by Floor using a Queue) -> O(N)
def level_order(root: TreeNode) -> list[list[int]]:
  if not root:
      return []
  q = deque([root])
  levels = []
  while q:
      level = []
      for _ in range(len(q)):
          node = q.popleft()
          level.append(node.val)
          if node.left: q.append(node.left)
          if node.right: q.append(node.right)
      levels.append(level)
  return levels

4. Core Interview Patterns

• Diameter / Max Path Sum (Postorder): At each node, update a global best using the path that curves through this node (left_h + right_h), and return the single best straight branch (1 + max(left_h, right_h)) up to the parent.
• Lowest Common Ancestor (LCA): If root is null, p, or q, return root. Recurse left and right: if both sides return non-null, root is the exact split point where p and q meet!

best = 0
def dfs(node: TreeNode) -> int:
  nonlocal best
  if not node: return 0
  left = max(0, dfs(node.left))
  right = max(0, dfs(node.right))
  best = max(best, node.val + left + right)  # Arch through node
  return node.val + max(left, right)         # Straight branch to parent

5. Practice On Your Own (Curated Submodule Problems)