Solving Maximum Depth of Binary Tree in Go: Step-by-Step Guide
The "Maximum Depth of Binary Tree" problem is one of the most foundational challenges you will encounter when learning tree data structures. It appears frequently in coding interviews, competitive programming, and real-world scenarios where hierarchical data needs to be measured. In this tutorial, we will explore what the problem is, why it matters, and how to solve it efficiently in Go using multiple approaches.
What Is the Maximum Depth of a Binary Tree?
A binary tree is a hierarchical data structure in which each node has at most two children, typically referred to as the left and right child. The maximum depth (also called the height) of a binary tree is the number of nodes along the longest path from the root node down to the farthest leaf node. A leaf node is a node with no children.
For example, consider the following binary tree:
3
/ \
9 20
/ \
15 7
The longest path is 3 -> 20 -> 7 (or 3 -> 20 -> 15), which contains 3 nodes. Therefore, the maximum depth is 3.
It is important to note that an empty tree (a tree with no nodes) has a maximum depth of 0. This edge case is critical and often trips up beginners.
Why Does This Problem Matter?
Understanding how to compute the depth of a binary tree is essential for several reasons:
- Foundation for recursion: This problem is a textbook example of how recursion can elegantly solve tree-based problems.
- Interview staple: It is one of the most commonly asked questions in technical interviews at major tech companies.
- Real-world applications: Depth calculations are used in file systems, DOM tree rendering, organizational hierarchies, and decision trees in machine learning.
- Building block: Many advanced tree problems, such as balanced tree checks and diameter calculations, build upon the concept of tree depth.
Defining the Tree Node Structure in Go
Before we can solve the problem, we need to define the structure of a binary tree node. In Go, we use a struct to represent each node, containing a value and pointers to its left and right children.
package main
import "fmt"
// TreeNode represents a node in a binary tree.
type TreeNode struct {
Val int
Left *TreeNode
Right *TreeNode
}
This simple struct is all we need. The Val field stores the integer value of the node, while Left and Right are pointers to child nodes. A nil pointer indicates the absence of a child.
Approach 1: Recursive Depth-First Search (DFS)
The most intuitive way to solve this problem is through recursion. The idea is simple: the maximum depth of a tree is 1 (for the current node) plus the maximum depth of its deeper subtree. If the current node is nil, the depth is 0.
Here is the recursive implementation:
// MaxDepth returns the maximum depth of a binary tree using recursion.
func MaxDepth(root *TreeNode) int {
// Base case: an empty tree has depth 0
if root == nil {
return 0
}
// Recursively compute the depth of left and right subtrees
leftDepth := MaxDepth(root.Left)
rightDepth := MaxDepth(root.Right)
// The depth of the current node is 1 plus the larger subtree depth
if leftDepth > rightDepth {
return 1 + leftDepth
}
return 1 + rightDepth
}
This approach is clean and easy to understand. Each call to MaxDepth explores one branch of the tree until it reaches a leaf, then bubbles the depth back up. The time complexity is O(n), where n is the number of nodes, because every node is visited exactly once. The space complexity is O(h), where h is the height of the tree, due to the recursion stack.
Approach 2: Iterative Breadth-First Search (BFS)
While recursion is elegant, it can cause stack overflow errors on very deep trees. An alternative is to use an iterative approach with breadth-first search. In this method, we traverse the tree level by level, incrementing a depth counter for each level we process.
Here is the BFS implementation using a queue:
// MaxDepthBFS returns the maximum depth using iterative breadth-first search.
func MaxDepthBFS(root *TreeNode) int {
if root == nil {
return 0
}
// Initialize a queue with the root node
queue := []*TreeNode{root}
depth := 0
for len(queue) > 0 {
depth++
// Number of nodes at the current level
levelSize := len(queue)
for i := 0; i < levelSize; i++ {
// Dequeue the front node
current := queue[0]
queue = queue[1:]
// Enqueue children if they exist
if current.Left != nil {
queue = append(queue, current.Left)
}
if current.Right != nil {
queue = append(queue, current.Right)
}
}
}
return depth
}
In this approach, we process all nodes at the current level before moving to the next. Each time we finish processing a level, we increment the depth counter. The time complexity remains O(n), and the space complexity is O(w), where w is the maximum width of the tree (the number of nodes at the widest level).
Approach 3: Iterative Depth-First Search with a Stack
If you prefer to mimic the recursive approach without actually using recursion, you can use an explicit stack. Each stack entry stores a node and its current depth. As we push children onto the stack, we track the maximum depth encountered.
// MaxDepthDFS returns the maximum depth using iterative depth-first search.
func MaxDepthDFS(root *TreeNode) int {
if root == nil {
return 0
}
type stackEntry struct {
node *TreeNode
depth int
}
stack := []stackEntry{{node: root, depth: 1}}
maxDepth := 0
for len(stack) > 0 {
// Pop the top entry
entry := stack[len(stack)-1]
stack = stack[:len(stack)-1]
if entry.depth > maxDepth {
maxDepth = entry.depth
}
// Push children with incremented depth
if entry.node.Left != nil {
stack = append(stack, stackEntry{node: entry.node.Left, depth: entry.depth + 1})
}
if entry.node.Right != nil {
stack = append(stack, stackEntry{node: entry.node.Right, depth: entry.depth + 1})
}
}
return maxDepth
}
This approach gives you fine-grained control over the traversal and avoids potential stack overflow issues. The time complexity is O(n) and the space complexity is O(h).
Putting It All Together: A Complete Example
Let us now write a complete Go program that builds a sample tree and tests all three approaches:
package main
import "fmt"
// TreeNode represents a node in a binary tree.
type TreeNode struct {
Val int
Left *TreeNode
Right *TreeNode
}
// MaxDepth returns the maximum depth using recursion.
func MaxDepth(root *TreeNode) int {
if root == nil {
return 0
}
leftDepth := MaxDepth(root.Left)
rightDepth := MaxDepth(root.Right)
if leftDepth > rightDepth {
return 1 + leftDepth
}
return 1 + rightDepth
}
// MaxDepthBFS returns the maximum depth using iterative BFS.
func MaxDepthBFS(root *TreeNode) int {
if root == nil {
return 0
}
queue := []*TreeNode{root}
depth := 0
for len(queue) > 0 {
depth++
levelSize := len(queue)
for i := 0; i < levelSize; i++ {
current := queue[0]
queue = queue[1:]
if current.Left != nil {
queue = append(queue, current.Left)
}
if current.Right != nil {
queue = append(queue, current.Right)
}
}
}
return depth
}
// MaxDepthDFS returns the maximum depth using iterative DFS.
func MaxDepthDFS(root *TreeNode) int {
if root == nil {
return 0
}
type stackEntry struct {
node *TreeNode
depth int
}
stack := []stackEntry{{node: root, depth: 1}}
maxDepth := 0
for len(stack) > 0 {
entry := stack[len(stack)-1]
stack = stack[:len(stack)-1]
if entry.depth > maxDepth {
maxDepth = entry.depth
}
if entry.node.Left != nil {
stack = append(stack, stackEntry{node: entry.node.Left, depth: entry.depth + 1})
}
if entry.node.Right != nil {
stack = append(stack, stackEntry{node: entry.node.Right, depth: entry.depth + 1})
}
}
return maxDepth
}
func main() {
// Build the sample tree:
// 3
// / \
// 9 20
// / \
// 15 7
root := &TreeNode{Val: 3}
root.Left = &TreeNode{Val: 9}
root.Right = &TreeNode{Val: 20}
root.Right.Left = &TreeNode{Val: 15}
root.Right.Right = &TreeNode{Val: 7}
fmt.Println("Recursive DFS depth:", MaxDepth(root))
fmt.Println("Iterative BFS depth:", MaxDepthBFS(root))
fmt.Println("Iterative DFS depth:", MaxDepthDFS(root))
// Test edge case: empty tree
fmt.Println("Empty tree depth:", MaxDepth(nil))
// Test edge case: single node
single := &TreeNode{Val: 1}
fmt.Println("Single node depth:", MaxDepth(single))
}
When you run this program, the output will be:
Recursive DFS depth: 3
Iterative BFS depth: 3
Iterative DFS depth: 3
Empty tree depth: 0
Single node depth: 1
Best Practices
When solving the maximum depth problem in Go, keep the following best practices in mind:
- Always handle the nil root case: An empty tree should return
0, not cause a panic. This is the most common edge case. - Prefer recursion for readability: Unless you are dealing with extremely deep trees that risk stack overflow, the recursive solution is the clearest and most maintainable.
- Use BFS for level-based problems: If your problem naturally involves levels (such as finding the width of a tree), BFS is a better fit since it processes nodes level by level.
- Avoid global variables: When using iterative approaches, keep state local to the function. This makes your code thread-safe and easier to test.
- Test with edge cases: Always test with an empty tree, a single-node tree, a left-skewed tree, a right-skewed tree, and a balanced tree to ensure correctness.
- Understand the trade-offs: Recursion uses the call stack (O(h) space), BFS uses a queue (O(w) space), and iterative DFS uses an explicit stack (O(h) space). Choose based on your constraints.
Common Pitfalls to Avoid
Even experienced developers can make mistakes with this problem. Here are some common pitfalls:
- Confusing depth and height: Some definitions count edges instead of nodes. Make sure you clarify whether the problem expects node count or edge count. The LeetCode version counts nodes.
- Forgetting to add 1: A frequent bug is returning the subtree depth without adding
1for the current node, which gives an off-by-one result. - Mutating the tree: Your depth function should be read-only. Avoid modifying node pointers or values during traversal.
- Inefficient queue operations: In Go, slicing the front of a slice (
queue[1:]) can be inefficient for large queues. For production code, consider usingcontainer/listor a ring buffer.
Optimizing Queue Operations in Go
The BFS implementation above uses slice operations that can be inefficient. For better performance, you can use a head index to avoid re-slicing:
func MaxDepthBFSOptimized(root *TreeNode) int {
if root == nil {
return 0
}
queue := []*TreeNode{root}
head := 0
depth := 0
for head < len(queue) {
depth++
levelSize := len(queue) - head
for i := 0; i < levelSize; i++ {
current := queue[head]
head++
if current.Left != nil {
queue = append(queue, current.Left)
}
if current.Right != nil {
queue = append(queue, current.Right)
}
}
}
return depth
}
By using a head index instead of re-slicing, we avoid the overhead of allocating new underlying arrays. This is a small but meaningful optimization when dealing with large trees.
Conclusion
Solving the Maximum Depth of Binary Tree problem in Go is an excellent way to build your understanding of tree traversal, recursion, and iterative algorithms. The recursive DFS approach is the most elegant and should be your default choice for clarity and simplicity. The iterative BFS and DFS approaches are valuable alternatives when you need to avoid recursion or when the problem has level-based requirements. By mastering all three methods and understanding their trade-offs in terms of time and space complexity, you will be well-equipped to tackle more advanced tree problems such as balanced tree validation, diameter calculation, and level-order traversal. Remember to always handle edge cases, test thoroughly, and choose the approach that best fits your specific constraints and performance needs.