ReviseAlgo Logo

Trees

Tree DFS & BFS

Master Depth-First Search (DFS) traversals and Breadth-First Search (BFS) level-order queue architectures.

Last Updated: August 2, 2026 • 15 min read

1. Introduction

What are Tree DFS and BFS?

  • Depth-First Search (DFS) traverses a tree by diving as deep as possible down a branch before backtracking.
  • Breadth-First Search (BFS) traverses a tree layer-by-layer, visiting all nodes at the current level before moving to the next level.

    • Why study them?

    These two search strategies are the foundations of almost all graph and tree algorithms. Choosing the correct traversal dictates how you solve problems: DFS is ideal for checking paths and heights, whereas BFS is ideal for finding shortest distances or grouping elements level-by-level.

    Where is it Used?

  • File System Searching: DFS is used to search for files inside nested directories.
  • Peer-to-Peer Networks: BFS is used to broadcast messages to neighbor nodes.

    • 2. Mental Models

    DFS: The Maze Explorer

    Imagine exploring a dark maze:
  • You walk down a path as far as you can.
  • When you hit a dead end, you take one step back (backtrack) and try the next available path.
  • You keep a list of paths in your hand (the recursive Call Stack) to remember where you came from.

    • BFS: The Water Ripple

    Imagine throwing a stone into a still pond:
  • The splash is the root node.
  • A ripple expands outward in a circle, hitting all points at distance 1, then distance 2, then distance 3.
  • The ripple expands level-by-level using a Queue to track the order of propagation.

    • 3. Core Algorithms & Implementations

    DFS Invariants (Recursive)

  • Pre-Order (Node -> Left -> Right): Process node before recursing.
  • In-Order (Left -> Node -> Right): Process node between subtrees (returns sorted order in BSTs).
  • Post-Order (Left -> Right -> Node): Process node after subtrees (ideal for bottom-up calculations like height).

    • BFS Level Order (Iterative)

    To group nodes level-by-level, we use a queue. Crucially, before processing a level, we record the size of the queue (levelSize). We only dequeue that many elements, ensuring we don't mix nodes from different levels as children are added.

    4. Visualizing Traversal Paths

    Consider tree [1, 2, 3, 4, 5]:

  • DFS Pre-order Path: 1 -> 2 -> 4 -> 5 -> 3 (Root -> Left Subtree -> Right Subtree).
  • DFS In-order Path: 4 -> 2 -> 5 -> 1 -> 3 (Left Leaf -> Parent -> Right Leaf -> Root).
  • DFS Post-order Path: 4 -> 5 -> 2 -> 3 -> 1 (Leaves -> Sub-parents -> Root).
  • BFS Level-order Path: Level 0: [1], Level 1: [2, 3], Level 2: [4, 5].

    • 5. Real-World Examples

  • HTML Render Trees: Browsers traverse DOM node elements using DFS to compute layout styles.
  • Network Broadcasting: Routing packets to all computers at distance 1 hops, then distance 2 hops using BFS.

    • 6. Interview Perspective

    How Interviewers Ask This Topic

    Interviewers test structure tracking:
  • "Given a binary tree, return the right side view." -> Use BFS. For each level, append the last element in that level to the result.
  • "Serialize and deserialize a binary tree." -> Use Pre-order DFS traversal. Encode null subtrees as #.

    • Common Mistakes

    Warning: 1. Forgetting to lock queue size in BFS: Writing for (int i = 0; i < queue.size(); i++) inside the while loop is bugged. The queue size changes as children are enqueued, mixing nodes from different levels.
    > 2. Space Complexity of Recursion Stack: Assuming DFS takes O(1) space. For a skewed tree of size N, the recursion call stack takes O(N) memory.

    7. Summary

  • DFS: NLR (Pre), LNR (In), LRN (Post). Uses stack (recursion).
  • BFS: Level-order. Uses queue.
  • Queue Size: Lock levelSize in BFS to process one level at a time.
  • Complexity: Time is O(N) for both; space is O(H) for DFS stack and O(W) for BFS queue width.

    • 8. Quiz

    Question 1: What is the maximum width space complexity of BFS? Answer: O(N) space, which occurs at the bottom level of a perfect binary tree, containing N/2 leaf nodes in the queue.
    Question 2: Which traversal prints a Binary Search Tree (BST) in sorted ascending order? Answer: In-order DFS traversal (Left -> Node -> Right).
    Question 3: How do you implement DFS iteratively? Answer: By maintaining an explicit Stack. Push the root. While the stack is not empty, pop a node, process it, and push its right child followed by its left child (left is pushed last so it is popped first).
    Question 4: True or False: BFS is preferred over DFS for finding the shortest path from the root to a leaf node in an unweighted tree. Answer: True. Since BFS visits nodes level-by-level, the first leaf node it encounters is guaranteed to be at the shortest depth.
    Question 5: What is the post-order traversal of a tree with only a root node and a left child? Answer: [left_child, root]. Post-order processes children before the parent.