Tree Traversal

Binary trees are traversed recursively (DFS) or level-by-level (BFS). Most tree problems reduce to choosing the right traversal and what to compute at each node.

Use when: you need to search, aggregate, or transform hierarchical data.

A binary tree node.

Inorder traversal (left, root, right) visits a BST’s nodes in sorted order. This is useful for validating BSTs or finding the kth smallest element.

Maximum depth shows the recursive pattern: the answer at each node depends on answers from its children. This “post-order” pattern (process children first) is the basis for most tree DP problems.

BFS (level-order traversal) uses a queue. It processes all nodes at depth d before any at depth d+1. Useful for shortest path in unweighted graphs and level-based tree problems.

Build this tree: 3 /
1 5 / \
0 2 7

type TreeNode struct {
	Val   int
	Left  *TreeNode
	Right *TreeNode
}
func inorder(root *TreeNode) []int {
	if root == nil {
		return nil
	}
	var result []int
	result = append(result, inorder(root.Left)...)
	result = append(result, root.Val)
	result = append(result, inorder(root.Right)...)
	return result
}
func maxDepth(root *TreeNode) int {
	if root == nil {
		return 0
	}

	leftDepth := maxDepth(root.Left)
	rightDepth := maxDepth(root.Right)

	if leftDepth > rightDepth {
		return leftDepth + 1
	}
	return rightDepth + 1
}
func levelOrder(root *TreeNode) [][]int {
	if root == nil {
		return nil
	}

	var result [][]int
	queue := []*TreeNode{root}

	for len(queue) > 0 {
		levelSize := len(queue)
		var level []int

		for i := 0; i < levelSize; i++ {
			node := queue[0]
			queue = queue[1:]

			level = append(level, node.Val)

			if node.Left != nil {
				queue = append(queue, node.Left)
			}
			if node.Right != nil {
				queue = append(queue, node.Right)
			}
		}

		result = append(result, level)
	}

	return result
}
func main() {
	root := &TreeNode{Val: 3,
		Left: &TreeNode{Val: 1,
			Left:  &TreeNode{Val: 0},
			Right: &TreeNode{Val: 2},
		},
		Right: &TreeNode{Val: 5,
			Right: &TreeNode{Val: 7},
		},
	}

	fmt.Println("Inorder:    ", inorder(root))
	fmt.Println("Max depth:  ", maxDepth(root))
	fmt.Println("Level order:", levelOrder(root))
}