name: Binary Tree Traversal
slug: tree-traversal
difficulty_level: 2
pattern_type: algorithm
display_order: 8

description: >
  Visit all nodes in a binary tree in specific orders: preorder (root-left-right),
  inorder (left-root-right), postorder (left-right-root), or level-order (BFS).
  Each order reveals different structural information about the tree.

when_to_use: |
  - Serializing/deserializing trees
  - Validating BST properties (inorder gives sorted order)
  - Computing tree properties (height, size, sum)
  - Copying or comparing trees
  - Path sum and path finding problems

metaphor: |
  Imagine reading a family tree. **Preorder** is like announcing yourself first,
  then introducing your children. **Inorder** is alphabetical—left child, then
  you, then right child. **Postorder** is like calculating taxes—you need to
  know your children's totals before computing your own.

  Another way to think about it: **preorder** is top-down (decisions flow from
  root to leaves), **postorder** is bottom-up (results bubble from leaves to root).

core_concept: |
  The three traversal orders differ only in *when* you process the current node
  relative to its children:

  - **Preorder**: Process **before** children → good for copying trees, prefix expressions
  - **Inorder**: Process **between** children → BST gives sorted order
  - **Postorder**: Process **after** children → good for deletion, evaluating expressions

  The key insight is that these traversals naturally map to different problems:

  - Need to see parents before children? → **Preorder**
  - Need to aggregate child results? → **Postorder**
  - Need sorted BST elements? → **Inorder**
  - Need level-by-level? → **BFS**

visualization: |
  **Example tree:**

  ```
        1
       / \
      2   3
     / \
    4   5
  ```

  **Preorder (Root → Left → Right):**
  ```
  Visit 1 → Visit 2 → Visit 4 → Visit 5 → Visit 3
  Result: [1, 2, 4, 5, 3]
  ```

  **Inorder (Left → Root → Right):**
  ```
  Visit 4 → Visit 2 → Visit 5 → Visit 1 → Visit 3
  Result: [4, 2, 5, 1, 3]

  For BST: gives elements in sorted order!
  ```

  **Postorder (Left → Right → Root):**
  ```
  Visit 4 → Visit 5 → Visit 2 → Visit 3 → Visit 1
  Result: [4, 5, 2, 3, 1]

  Children processed before parent—useful for computing heights/sizes.
  ```

  **Level-order (BFS):**
  ```
  Level 0: [1]
  Level 1: [2, 3]
  Level 2: [4, 5]
  Result: [1, 2, 3, 4, 5]
  ```

code_template: |
  from collections import deque

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


  def preorder_recursive(root: TreeNode) -> list:
      """Preorder: Root → Left → Right"""
      if not root:
          return []
      return ([root.val]
              + preorder_recursive(root.left)
              + preorder_recursive(root.right))


  def preorder_iterative(root: TreeNode) -> list:
      """Iterative preorder using stack."""
      if not root:
          return []

      result = []
      stack = [root]

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

      return result


  def inorder_recursive(root: TreeNode) -> list:
      """Inorder: Left → Root → Right"""
      if not root:
          return []
      return (inorder_recursive(root.left)
              + [root.val]
              + inorder_recursive(root.right))


  def inorder_iterative(root: TreeNode) -> list:
      """Iterative inorder using stack."""
      result = []
      stack = []
      current = root

      while current or stack:
          # Go left as far as possible
          while current:
              stack.append(current)
              current = current.left

          # Process current node
          current = stack.pop()
          result.append(current.val)

          # Move to right subtree
          current = current.right

      return result


  def postorder_recursive(root: TreeNode) -> list:
      """Postorder: Left → Right → Root"""
      if not root:
          return []
      return (postorder_recursive(root.left)
              + postorder_recursive(root.right)
              + [root.val])


  def postorder_iterative(root: TreeNode) -> list:
      """Iterative postorder using two stacks."""
      if not root:
          return []

      result = []
      stack = [root]

      while stack:
          node = stack.pop()
          result.append(node.val)
          if node.left:
              stack.append(node.left)
          if node.right:
              stack.append(node.right)

      return result[::-1]  # Reverse for postorder


  def level_order(root: TreeNode) -> list[list]:
      """Level-order traversal using BFS."""
      if not root:
          return []

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

      while queue:
          level = []
          for _ in range(len(queue)):
              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

recognition_signals:
  - "binary tree"
  - "tree traversal"
  - "preorder"
  - "inorder"
  - "postorder"
  - "level order"
  - "serialize tree"
  - "flatten tree"
  - "BST to sorted"
  - "kth smallest in BST"
  - "validate BST"
  - "path sum"

common_mistakes:
  - title: Stack order in iterative preorder
    description: |
      Pushing left child before right child processes right first because
      stacks are LIFO.
    fix: |
      Push right child first, then left child:
      ```python
      if node.right:
          stack.append(node.right)  # Push right first
      if node.left:
          stack.append(node.left)   # Left popped first
      ```

  - title: Iterative inorder is tricky
    description: |
      The iterative inorder traversal is harder to get right than preorder or
      postorder because you need to track when to go left vs when to process.
    fix: |
      Use the "go left until null, then process and go right" pattern:
      ```python
      while current or stack:
          while current:
              stack.append(current)
              current = current.left
          current = stack.pop()
          process(current)
          current = current.right
      ```

  - title: Forgetting null checks
    description: |
      Accessing `node.left` or `node.right` without checking if node is None
      causes attribute errors.
    fix: |
      Always check for null nodes first:
      ```python
      if not root:
          return []
      ```

  - title: Modifying tree during traversal
    description: |
      Changing node values or structure while traversing can cause missed nodes
      or infinite loops.
    fix: |
      Collect nodes to modify in a separate pass, or use a traversal that
      processes children before modifying the parent.

variations:
  - name: Morris Traversal
    description: |
      Inorder traversal using O(1) space by temporarily modifying the tree
      (threading right pointers to inorder successors).
    example: "Recover Binary Search Tree, Inorder without stack"

  - name: Boundary Traversal
    description: |
      Traverse only the boundary of the tree: left boundary, leaves, right
      boundary in reverse.
    example: "Boundary of Binary Tree"

  - name: Vertical Order Traversal
    description: |
      Group nodes by their horizontal distance from root. Nodes at same
      horizontal distance are in the same vertical line.
    example: "Vertical Order Traversal, Binary Tree Right Side View"

  - name: Zigzag Level Order
    description: |
      Level-order but alternating direction: left-to-right, then right-to-left,
      and so on.
    example: "Binary Tree Zigzag Level Order Traversal"

  - name: Tree Serialization
    description: |
      Use traversal order to convert tree to string and back. Preorder with
      null markers is common.
    example: "Serialize and Deserialize Binary Tree"

related_patterns:
  - dfs
  - bfs

prerequisite_patterns: []
