Solving Diameter of Binary Tree in Go: Step-by-Step Guide
The Diameter of Binary Tree problem is one of the most popular algorithmic challenges you will encounter in coding interviews and competitive programming. It asks you to find the longest path between any two nodes in a binary tree, measured by the number of edges traversed. In this tutorial, we will walk through the problem, understand the underlying intuition, and implement an efficient solution in Go.
What Is the Diameter of a Binary Tree?
The diameter (also called the "width") of a binary tree is the length of the longest path between any two nodes in the tree. This path may or may not pass through the root. The length is measured in terms of the number of edges between the two endpoints, not the number of nodes.
For example, consider the following binary tree:
1
/ \
2 3
/ \
4 5
/
6
The longest path here goes from node 6 to node 3, passing through nodes 4, 2, and 1. The number of edges on this path is 4, so the diameter is 4.
Why Does This Problem Matter?
The diameter problem is a classic example of tree traversal and recursion. It teaches several important concepts:
- Recursive thinking: Breaking a large problem into smaller subproblems on subtrees.
- Post-order traversal: Computing results from the bottom up by processing children before the parent.
- Global state management: Tracking a maximum value across recursive calls.
- Time and space complexity analysis: Understanding the cost of recursive solutions.
These skills transfer directly to many real-world scenarios, such as analyzing network topologies, organizational hierarchies, file systems, and any domain where hierarchical data structures appear.
Understanding the Approach
The key insight is that for any given node, the longest path that passes through it is the sum of the depths of its left and right subtrees. Therefore, at each node, we can compute a candidate diameter as leftDepth + rightDepth and keep track of the maximum candidate seen so far.
To compute the depth of each subtree, we use a recursive helper function. The depth of a node is 1 + max(leftDepth, rightDepth). While computing depths, we simultaneously update the global diameter.
This leads to a clean post-order traversal where each node is visited after its children, allowing us to combine the results from both subtrees at every step.
Defining the Tree Structure in Go
Before writing the algorithm, we need a way to represent a binary tree. In Go, we use a struct with pointers to 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
}
Each TreeNode holds an integer value and optional pointers to its left and right children. A nil pointer indicates the absence of a child.
Implementing the Diameter Function
Now let us implement the function that computes the diameter. We will use a helper function that returns the depth of a subtree while updating a pointer to the maximum diameter found so far.
// diameterOfBinaryTree returns the diameter of the binary tree.
func diameterOfBinaryTree(root *TreeNode) int {
diameter := 0
depth(root, &diameter)
return diameter
}
// depth returns the depth of the subtree rooted at node
// and updates the diameter pointer with the maximum path found.
func depth(node *TreeNode, diameter *int) int {
if node == nil {
return 0
}
leftDepth := depth(node.Left, diameter)
rightDepth := depth(node.Right, diameter)
// The longest path passing through this node uses
// the deepest path on each side.
currentPath := leftDepth + rightDepth
if currentPath > *diameter {
*diameter = currentPath
}
// Return the depth of this subtree.
if leftDepth > rightDepth {
return leftDepth + 1
}
return rightDepth + 1
}
Notice how the depth function does two jobs at once: it returns the depth of the current subtree, and it updates the diameter variable passed by pointer. This avoids recomputing depths and keeps the solution efficient.
Putting It All Together
Let us write a complete program that builds a sample tree, computes its diameter, and prints the result:
package main
import "fmt"
type TreeNode struct {
Val int
Left *TreeNode
Right *TreeNode
}
func diameterOfBinaryTree(root *TreeNode) int {
diameter := 0
depth(root, &diameter)
return diameter
}
func depth(node *TreeNode, diameter *int) int {
if node == nil {
return 0
}
leftDepth := depth(node.Left, diameter)
rightDepth := depth(node.Right, diameter)
currentPath := leftDepth + rightDepth
if currentPath > *diameter {
*diameter = currentPath
}
if leftDepth > rightDepth {
return leftDepth + 1
}
return rightDepth + 1
}
func main() {
// Build the tree:
// 1
// / \
// 2 3
// / \
// 4 5
// /
// 6
root := &TreeNode{Val: 1}
root.Left = &TreeNode{Val: 2}
root.Right = &TreeNode{Val: 3}
root.Left.Left = &TreeNode{Val: 4}
root.Left.Right = &TreeNode{Val: 5}
root.Left.Left.Left = &TreeNode{Val: 6}
fmt.Println("Diameter:", diameterOfBinaryTree(root)) // Output: 4
}
When you run this program, it prints Diameter: 4, which matches our manual calculation.
Alternative Approach Using a Struct Return
Some developers prefer avoiding mutable pointers by returning a struct that carries both the depth and the current best diameter. This is a more functional style and can be easier to reason about in concurrent contexts:
type result struct {
depth int
diameter int
}
func diameterOfBinaryTreeAlt(root *TreeNode) int {
return compute(root).diameter
}
func compute(node *TreeNode) result {
if node == nil {
return result{depth: 0, diameter: 0}
}
left := compute(node.Left)
right := compute(node.Right)
currentDepth := left.depth
if right.depth > currentDepth {
currentDepth = right.depth
}
currentDepth++
pathThroughNode := left.depth + right.depth
bestDiameter := left.diameter
if right.diameter > bestDiameter {
bestDiameter = right.diameter
}
if pathThroughNode > bestDiameter {
bestDiameter = pathThroughNode
}
return result{depth: currentDepth, diameter: bestDiameter}
}
This version is slightly more verbose but eliminates shared mutable state, which some teams prefer for clarity and safety.
Complexity Analysis
Both implementations visit each node exactly once, so the time complexity is O(n), where n is the number of nodes in the tree. The space complexity is O(h), where h is the height of the tree, due to the recursion stack. In the worst case of a skewed tree, h equals n, giving O(n) space. For a balanced tree, the space complexity is O(log n).
Best Practices
- Handle nil roots explicitly: Always check for a
nilnode at the start of your recursive function to avoid nil pointer dereferences. - Separate concerns: Keep the public function (
diameterOfBinaryTree) clean and push the recursion into a helper. This makes the API easy to use. - Use pointers for accumulators: When you need to track a value across recursive calls in Go, passing a pointer is idiomatic and efficient.
- Test edge cases: Verify your solution with an empty tree, a single-node tree, a left-skewed tree, a right-skewed tree, and a balanced tree.
- Avoid global variables: Package-level variables can cause subtle bugs when the function is called multiple times. Prefer passing the accumulator as a parameter.
- Comment the recurrence: Clearly document the recurrence relation so future maintainers understand why the solution works.
Common Pitfalls
One frequent mistake is confusing the number of nodes with the number of edges. The diameter is defined in terms of edges, so a single-node tree has a diameter of 0, not 1. Make sure your base case returns 0 for a nil node and that you add 1 only when returning the depth, not when computing the path length.
Another pitfall is assuming the diameter always passes through the root. While this is true for some trees, it is not guaranteed. The recursive approach handles this correctly because it checks the longest path through every node, not just the root.
Testing the Implementation
Here is a small test suite using Go's built-in testing package to validate the implementation across several scenarios:
package main
import "testing"
func TestDiameter(t *testing.T) {
tests := []struct {
name string
tree *TreeNode
want int
}{
{"empty tree", nil, 0},
{"single node", &TreeNode{Val: 1}, 0},
{"two nodes", &TreeNode{Val: 1, Left: &TreeNode{Val: 2}}, 1},
{"balanced tree", buildBalanced(), 2},
{"left skewed", buildLeftSkewed(), 3},
{"complex tree", buildComplex(), 4},
}
for _, tc := range tests {
t.Run(tc.name, func(t *testing.T) {
got := diameterOfBinaryTree(tc.tree)
if got != tc.want {
t.Errorf("got %d, want %d", got, tc.want)
}
})
}
}
func buildBalanced() *TreeNode {
return &TreeNode{
Val: 1,
Left: &TreeNode{Val: 2},
Right: &TreeNode{Val: 3},
}
}
func buildLeftSkewed() *TreeNode {
return &TreeNode{
Val: 1,
Left: &TreeNode{
Val: 2,
Left: &TreeNode{
Val: 3,
Left: &TreeNode{Val: 4},
},
},
}
}
func buildComplex() *TreeNode {
root := &TreeNode{Val: 1}
root.Left = &TreeNode{Val: 2}
root.Right = &TreeNode{Val: 3}
root.Left.Left = &TreeNode{Val: 4}
root.Left.Right = &TreeNode{Val: 5}
root.Left.Left.Left = &TreeNode{Val: 6}
return root
}
Run the tests with go test -v to confirm that every case passes. Writing tests like these is essential for catching regressions when you refactor the code later.
Conclusion
The Diameter of Binary Tree problem is a beautiful example of how a single post-order traversal can solve what initially seems like a complex question. By computing subtree depths recursively and tracking the maximum path through each node, we arrive at an elegant O(n) solution in Go. Whether you prefer the pointer-based accumulator style or the struct-return style, the underlying principle remains the same: combine results from children, update a global best, and return the depth to your caller. Master this pattern, and you will be well equipped to tackle a wide family of tree problems, including longest paths, balanced tree checks, and subtree aggregations.