BeginnerTrees

Tree DFS (Depth-First Search)

Traverse trees using preorder, inorder, or postorder to solve tree-based problems

Time: O(n)
Space: O(h)
Pattern Overview

Core Idea

Tree DFS explores as far as possible along each branch before backtracking. Three main traversal orders exist: preorder (root-left-right), inorder (left-root-right), and postorder (left-right-root). Each order is useful for different problem types.

When to Use

Use DFS for tree traversal problems, finding paths, calculating tree properties (height, diameter), validating tree structures, or when you need to process nodes in a specific order. Particularly effective for problems requiring bottom-up or top-down information flow.

General Recognition Cues
General indicators that this pattern might be applicable
  • Need to traverse entire tree or find specific paths
  • Calculate tree properties (height, diameter, sum)
  • Validate tree structure (BST, balanced, symmetric)
  • Find root-to-leaf paths or path sums
  • Serialize/deserialize tree structures
  • Problems involving subtrees or tree transformations
Pattern Variants & Approaches
Different methodologies and implementations for this pattern
1

Preorder Traversal (Root-Left-Right)

Process root before visiting children, useful for copying trees

When to Use This Variant
  • Need to process parent before children
  • Tree serialization/copying
  • Prefix expression evaluation
  • Top-down tree construction
  • Path tracking from root
Use Case
Tree serialization, creating copies, prefix expression evaluation
Advantages
  • Natural for top-down problems
  • Easy to implement recursively
  • Good for tree construction
  • Processes parent before children
Implementation
def preorder(root, result=[]):
      if not root:
          return
      
      # Process root first
      result.append(root.val)
      
      # Then left subtree
      preorder(root.left, result)
      
      # Then right subtree
      preorder(root.right, result)
      
      return result
  
  # Iterative version
  def preorder_iterative(root):
      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
2

Inorder Traversal (Left-Root-Right)

Process left subtree, then root, then right subtree

When to Use This Variant
  • Binary Search Tree (BST) problems
  • Need sorted order of elements
  • BST validation required
  • Infix expression evaluation
  • Range queries in BST
Use Case
BST traversal (gives sorted order), expression tree evaluation
Advantages
  • Produces sorted sequence for BST
  • Natural for BST validation
  • Useful for range queries
  • Standard for infix notation
Implementation
def inorder(root, result=[]):
      if not root:
          return
      
      # Left subtree first
      inorder(root.left, result)
      
      # Process root
      result.append(root.val)
      
      # Right subtree last
      inorder(root.right, result)
      
      return result
  
  # Iterative version
  def inorder_iterative(root):
      result = []
      stack = []
      current = root
      
      while current or stack:
          # Go to leftmost node
          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
3

Postorder Traversal (Left-Right-Root)

Process children before root, useful for bottom-up calculations

When to Use This Variant
  • Need to process children before parent
  • Bottom-up calculations (height, sum)
  • Tree deletion or cleanup
  • Postfix expression evaluation
  • Subtree property aggregation
Use Case
Deleting trees, calculating subtree properties, postfix evaluation
Advantages
  • Natural for bottom-up problems
  • Children processed before parent
  • Good for tree deletion
  • Useful for aggregation problems
Implementation
def postorder(root, result=[]):
      if not root:
          return
      
      # Left subtree first
      postorder(root.left, result)
      
      # Right subtree second
      postorder(root.right, result)
      
      # Process root last
      result.append(root.val)
      
      return result
  
  # Iterative version (using two stacks)
  def postorder_iterative(root):
      if not root:
          return []
      
      result = []
      stack1 = [root]
      stack2 = []
      
      while stack1:
          node = stack1.pop()
          stack2.append(node)
          
          if node.left:
              stack1.append(node.left)
          if node.right:
              stack1.append(node.right)
      
      while stack2:
          result.append(stack2.pop().val)
      
      return result
Common Pitfalls
Watch out for these common mistakes
  • Not handling null/empty nodes properly
  • Confusing the three traversal orders and their use cases
  • Stack overflow with very deep trees (use iterative approach)
  • Not properly passing state down or bubbling results up
  • Forgetting to return values from recursive calls
Code Templates
Compare implementations across different languages
def dfs_preorder(root):
      if not root:
          return
      
      # Process current node (preorder)
      result.append(root.val)
      
      # Recurse on children
      dfs_preorder(root.left)
      dfs_preorder(root.right)
  
  def dfs_inorder(root):
      if not root:
          return
      
      dfs_inorder(root.left)
      result.append(root.val)  # Process (inorder)
      dfs_inorder(root.right)
  
  def dfs_postorder(root):
      if not root:
          return
      
      dfs_postorder(root.left)
      dfs_postorder(root.right)
      result.append(root.val)  # Process (postorder)
Example Problems
Classic LeetCode problems using this pattern
Complexity Analysis
Time Complexity
O(n)

Visit each node exactly once, where n is the number of nodes in the tree.

Space Complexity
O(h)

Recursion stack depth equals tree height h. O(log n) for balanced trees, O(n) for skewed trees.

Ready to test your knowledge?

Test your pattern recognition with interactive questions