🧭 DSA Pattern #8 — Tree Traversal Patterns (DFS & BFS Simplified)

Tree problems appear constantly in coding interviews, from beginner to senior levels. I have always felt a little overwhelmed dealing with trees because of the sheer variety — Binary Trees, Binary Search Trees (BSTs), AVL trees, B-Trees, and many more.

And then there are traversals like preorder, inorder, postorder, and level order…

So the way I deal with that is by going back to the basics and really understanding the core patterns: Depth First Search (DFS) and Breadth First Search (BFS).

AI Generated Image

🌱 Before You Start

This article assumes a basic familiarity with binary trees:

• What is a binary tree
• Difference between a binary tree and a Binary Search Tree (BST)
• Terms like root, leaf, parent, child, height, and depth

If these concepts are new to you, a quick learning first will help this article click faster. If you understand better with visualisations and examples, do check out VisuAlgo, which has excellent tree visualizations.

Once you’re comfortable with those basics, you are ready to get into traversal patterns.

💡 The Core Idea

Most tree problems can be approached using one of these two traversal strategies.

1. DFS (Depth First Search)

Go as deep as possible along one branch before backtracking.

Think: Explore children first, then come back.

One simple hack to remember the three DFS traversals:

Pre, In, and Post all describe where the Root is visited.

• Preorder → visit Root before subtrees →* *Root, Left, Right
• Inorder → visit Root in between subtrees → Left, Root, Right
• Postorder → visit Root after subtrees → Left, Right, Root

Often implemented using simple recursion.

2. BFS (Breadth First Search)

Visit nodes level by level.

Think:

Explore neighbors first before going deeper.

Usually implemented using a queue.

🧩 When Should This Pattern Come to Mind?

Think DFS or BFS when a problem involves:

• Tree traversal
• Path-related problems
• Tree height or depth
• Level-order processing
• Validating or searching trees
• Lowest common ancestor
• Serialize/deserialize trees

⚙️ Basic Tree Structure

Before solving tree problems, let’s define a node structure.

type TreeNode struct {
    Val   int
    Left  *TreeNode
    Right *TreeNode
}

Each node stores:

• a value
• pointer to left child
• pointer to right child

Trees are simply nodes connected hierarchically.

📘 Example 1 — DFS Preorder Traversal

Visit:

Root → Left → Right

func preorder(root *TreeNode) {
    if root == nil {
      return
    }
    fmt.Println(root.Val)
    preorder(root.Left)
    preorder(root.Right)
}

🧠 Key idea

Process the current node first. Then recursively explore left and right. Recursion naturally handles backtracking.

Time Complexity → O(n) Space Complexity → O(h) (h = tree height)

📘 Example 2 — Lowest Common Ancestor (Classic DFS Pattern)

func lowestCommonAncestor(root, p, q *TreeNode) *TreeNode {
    if root == nil || root == p || root == q {
        return root
    }

    left := lowestCommonAncestor(root.Left, p, q)
    right := lowestCommonAncestor(root.Right, p, q)

    if left != nil && right != nil {
        return root
    }

    if left != nil {
        return left
    }

    return right
}

🧠 Key idea

Think of DFS searching both subtrees:

• Search left subtree for p or q
• Search right subtree for p or q

Three scenarios can happen:

1. p and q are found in different subtrees

The current node is their Lowest Common Ancestor.

2. Both are in the left subtree

Return the result found in the left subtree.

3. Both are in the right subtree

Return the result found in the right subtree.

This “propagate results upward through recursion” pattern appears often in tree problems.

Time Complexity → O(n) Space Complexity → O(h)

📘 Example 3 — BFS Level Order Traversal

Classic BFS.

func levelOrder(root *TreeNode) [][]int {
   if root == nil {
      return [][]int{}
   }

   queue := []*TreeNode{root}
   res := [][]int{}

   for len(queue) > 0 {

      cur := []int{}
      levelSize := len(queue)

      for i := 0; i < levelSize; i++ {

         visited := queue[0]
         queue = queue[1:]
         cur = append(cur, visited.Val)

         if visited.Left != nil {
            queue = append(queue, visited.Left)
         }
         if visited.Right != nil {
            queue = append(queue, visited.Right)
         }
      }
      res = append(res, cur)
   }
   return res
}

🧠 Key idea

Use a queue. Process one level at a time.

Push children into the queue for the next level. That naturally gives level-order traversal.

Time Complexity → O(n) Space Complexity → O(w) (w = maximum width of the tree)

📘 Example 4 — Minimum Depth (BFS in Action)

Sometimes BFS is a better fit than DFS. Recognising that comes with practice.

func minDepth(root *TreeNode) int {

    if root == nil {
        return 0
    }

    type Pair struct {
        node  *TreeNode
        depth int
    }

    queue := []Pair{{root,1}}

    for len(queue) > 0 {

        curr := queue[0]
        queue = queue[1:]

        node := curr.node
        depth := curr.depth

        if node.Left == nil && node.Right == nil {
            return depth
        }

        if node.Left != nil {
            queue = append(queue, Pair{
                node.Left,
                depth+1,
            })
        }

        if node.Right != nil {
            queue = append(queue, Pair{
                node.Right,
                depth+1,
            })
        }
    }

    return 0
}

🧠 Key idea

• Early termination: BFS explores level by level, so the first leaf found is guaranteed to be at the minimum depth.
• Efficient for uneven trees: BFS can find a shallow leaf quickly, while DFS may waste time exploring deep branches before reaching it.

Time Complexity → O(n) Space Complexity → O(w)

⭐ Important BST Pattern — Inorder Successor

This is a classic interview problem that combines inorder traversal intuition with BST properties (left < root < right). An inorder successor is the node that comes immediately after the target node when doing an inorder traversal.

func inorderSuccessor(root, p *TreeNode) *TreeNode {
    var successor *TreeNode

    for root != nil {

        if p.Val < root.Val {
            successor = root
            root = root.Left
        } else {
            root = root.Right
        }
   }
}

🧠 Key idea

Use BST ordering:

• If current node is greater than target, it could be a successor.
• Move left to try finding a smaller valid successor.
• Otherwise move right.

🧗 Practice Problems (Easy → Hard)

Beginner

• Maximum Depth of Binary Tree
• Same Tree
• Invert Binary Tree

Intermediate

• Binary Tree Right Side View
• Binary Tree Zigzag Level Order Traversal
• Path Sum
• Validate Binary Search Tree

Advanced

• Construct Binary Tree from Preorder and Inorder Traversal
• Binary Tree Maximum Path Sum
• Serialize and Deserialize Binary Tree

🧠 Final Takeaway

Most tree interview problems reduce to two patterns:

• DFS → go deep till the end
• BFS → go level by level

Different problems may look very different on the surface, but under the hood, many are simply variations of these two patterns.

Whenever you see a tree problem, ask:

Use:

Is this naturally DFS or BFS?

That question often leads directly to the solution.

☕ Support My Writing

If you reached this far and liked what you read, you can support me here:

👉 Buy Me a Coffee

You can also use the Medium Support button above.