Depth-First Search (DFS)

The depth-first search algorithm is used to traverse or search tree/graph data structures by exploring as far as possible along each branch before backtracking.

Time Complexity: $O(n)$

Space Complexity: $O(h)$, where h is the height of the tree

Implementation

Python

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

def dfs(node):
    if not node:
        return
    # Process current node
    print(node.val)  
    # Recursively process left and right subtrees
    dfs(node.left)
    dfs(node.right)

Golang

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

func dfs(node *TreeNode) {
    if node == nil {
        return
    }
    // Process current node
    fmt.Println(node.Val)
    // Recursively process left and right subtrees
    dfs(node.Left)
    dfs(node.Right)
}