Depth-First Search (DFS)

DFS explores every subtree until it hits a dead end before switching to another path. It can be done recursively, or it can be done iteratively.

Let’s reuse the TreeNode definition from our BFS post.

type TreeNode[T comparable] struct {
    Val T
    Left *TreeNode
    Right *TreeNode
}

type TreeNode[T comparable] struct {
    Val T
    Left *TreeNode
    Right *TreeNode
}

1. Recursive Solution

func DFS[T comparable](root *TreeNode[T], target T) *TreeNode[T] {
    if root == nil || root.Val == target {
        return root
    }
    
    // search left
    if found := DFS(root.Left); found != nil {
        return found
    }
    
    // search right
    return DFS(root.Right)
}

func DFS[T comparable](root *TreeNode[T], target T) *TreeNode[T] {
    if root == nil || root.Val == target {
        return root
    }
    
    // search left
    if found := DFS(root.Left); found != nil {
        return found
    }
    
    // search right
    return DFS(root.Right)
}

The recursive approach achieves $O(n)$ time in the worst case, $O(\log n)$ space in the best case, and $O(n)$ space in the worst case.

The space complexity can range from $O(\log n)$ to $O(n)$ because a binary tree can be perfectly balanced, or it can be absolutely skewed like a linked list.

2. Iterative Solution

func DFS[T comparable](root *TreeNode[T], target T) *TreeNode[T] {
    if root == nil {
        return nil
    }

    // a stack to mimic call stack - LIFO
    stack := []*TreeNode[T]{ root }

    for len(stack) > 0 {
        // pop the last-in node
        curr := stack[len(stack)-1]
        stack[len(stack)-1] = nil    // memory leak prevention
        stack = stack[:len(stack)-1]
        
        if curr.Val == target {
            return curr
        }
        
        // push children to stack
        // left child last-in first-out
        if curr.Right != nil {
            stack = append(stack, curr.Right)
        }
        if curr.Left != nil {
            stack = append(stack, curr.Left)
        }
    }

    return nil
}

func DFS[T comparable](root *TreeNode[T], target T) *TreeNode[T] {
    if root == nil {
        return nil
    }

    // a stack to mimic call stack - LIFO
    stack := []*TreeNode[T]{ root }

    for len(stack) > 0 {
        // pop the last-in node
        curr := stack[len(stack)-1]
        stack[len(stack)-1] = nil    // memory leak prevention
        stack = stack[:len(stack)-1]
        
        if curr.Val == target {
            return curr
        }
        
        // push children to stack
        // left child last-in first-out
        if curr.Right != nil {
            stack = append(stack, curr.Right)
        }
        if curr.Left != nil {
            stack = append(stack, curr.Left)
        }
    }

    return nil
}

The iterative approach achieves the same $O(n)$ time complexity, as well as $O(\log n)$ space in the best case and $O(n)$ space in the worst case. However, because the custom stack stores only raw node pointers, its memory footprint per element is significantly smaller than the overhead of a recursive function call stack frame. Furthermore, since the custom stack utilizes heap memory rather than the limited thread/goroutine call stack, it eliminates the risk of stack overflow and is far more reliable for deep trees or large input sizes.

I still like the recursive solution because it’s far more readable. (Nah, kidding!)

Ordering is important in DFS sometimes. The example explores in the parent > left > right order, which is called pre-order.

There’s also post-order: left > right > parent ; and

in-order: left > parent > right.

Bye!