Solving Symmetric Tree in Go: Step-by-Step Guide
The Symmetric Tree problem is one of the most popular algorithmic challenges you will encounter in coding interviews and competitive programming. It tests your understanding of tree data structures, recursion, and breadth-first traversal techniques. In this tutorial, we will explore how to determine whether a binary tree is symmetric around its center using the Go programming language.
What Is a Symmetric Tree?
A binary tree is considered symmetric if it is a mirror reflection of itself around its root. This means that the left subtree must be a mirror reflection of the right subtree. For a tree to be symmetric, every node at the corresponding position on both sides must have the same value, and their children must be mirrored accordingly.
Consider the following example of a symmetric tree:
1
/ \
2 2
/ \ / \
3 4 4 3
This tree is symmetric because the left subtree of the root is a mirror of the right subtree. Now consider an asymmetric tree:
1
/ \
2 2
\ \
3 3
This tree is not symmetric because the structure of the left and right subtrees does not mirror each other, even though the values match.
Why the Symmetric Tree Problem Matters
Understanding how to solve the Symmetric Tree problem is important for several reasons:
- Interview relevance: It is a classic problem frequently asked by companies like Amazon, Google, and Microsoft.
- Recursion mastery: It reinforces your ability to think recursively and break problems into smaller subproblems.
- Tree traversal skills: It deepens your understanding of depth-first and breadth-first traversal strategies.
- Real-world applications: Symmetry checks are useful in graphics rendering, data validation, and structural analysis.
Defining the Tree Structure in Go
Before we can solve the problem, we need to define a binary tree node structure in Go. We will use a struct with a value and 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
}
This simple struct will serve as the foundation for all the solutions we explore in this tutorial.
Approach 1: Recursive Solution
The recursive approach is the most intuitive way to solve the Symmetric Tree problem. The idea is to compare the left and right subtrees of the root recursively. Two trees are mirrors of each other if:
- Both roots are nil, meaning both subtrees are empty.
- Both roots have the same value, and the left subtree of one is a mirror of the right subtree of the other.
Here is the complete implementation:
package main
import "fmt"
type TreeNode struct {
Val int
Left *TreeNode
Right *TreeNode
}
// isMirror checks whether two trees are mirror images of each other.
func isMirror(t1, t2 *TreeNode) bool {
// If both nodes are nil, they are mirrors.
if t1 == nil && t2 == nil {
return true
}
// If only one node is nil, they are not mirrors.
if t1 == nil || t2 == nil {
return false
}
// Both nodes must have the same value, and their children must be mirrors.
return t1.Val == t2.Val &&
isMirror(t1.Left, t2.Right) &&
isMirror(t1.Right, t2.Left)
}
// isSymmetric determines if a binary tree is symmetric around its center.
func isSymmetric(root *TreeNode) bool {
if root == nil {
return true
}
return isMirror(root.Left, root.Right)
}
func main() {
// Build a symmetric tree:
// 1
// / \
// 2 2
// / \ / \
// 3 4 4 3
root := &TreeNode{Val: 1}
root.Left = &TreeNode{Val: 2}
root.Right = &TreeNode{Val: 2}
root.Left.Left = &TreeNode{Val: 3}
root.Left.Right = &TreeNode{Val: 4}
root.Right.Left = &TreeNode{Val: 4}
root.Right.Right = &TreeNode{Val: 3}
fmt.Println("Is symmetric:", isSymmetric(root)) // Output: true
}
The time complexity of this solution is O(n), where n is the number of nodes in the tree, because we visit each node exactly once. The space complexity is O(h), where h is the height of the tree, due to the recursion stack.
Approach 2: Iterative Solution Using a Queue
While the recursive solution is elegant, some scenarios require an iterative approach to avoid stack overflow on very deep trees. We can use a queue to perform a breadth-first comparison of corresponding nodes.
The strategy is to enqueue pairs of nodes that should be mirrors of each other. For each pair we dequeue, we check whether their values match and whether their children are enqueued in the correct mirrored order.
package main
import (
"container/list"
"fmt"
)
type TreeNode struct {
Val int
Left *TreeNode
Right *TreeNode
}
// isSymmetricIterative uses a queue to check symmetry iteratively.
func isSymmetricIterative(root *TreeNode) bool {
if root == nil {
return true
}
queue := list.New()
queue.PushBack(root.Left)
queue.PushBack(root.Right)
for queue.Len() > 0 {
// Dequeue two nodes that should be mirrors of each other.
n1 := queue.Remove(queue.Front()).(*TreeNode)
n2 := queue.Remove(queue.Front()).(*TreeNode)
// Both nil means this pair is symmetric so far.
if n1 == nil && n2 == nil {
continue
}
// One nil means asymmetric structure.
if n1 == nil || n2 == nil {
return false
}
// Values must match.
if n1.Val != n2.Val {
return false
}
// Enqueue children in mirrored order.
queue.PushBack(n1.Left)
queue.PushBack(n2.Right)
queue.PushBack(n1.Right)
queue.PushBack(n2.Left)
}
return true
}
func main() {
// Build an asymmetric tree:
// 1
// / \
// 2 2
// \ \
// 3 3
root := &TreeNode{Val: 1}
root.Left = &TreeNode{Val: 2}
root.Right = &TreeNode{Val: 2}
root.Left.Right = &TreeNode{Val: 3}
root.Right.Right = &TreeNode{Val: 3}
fmt.Println("Is symmetric:", isSymmetricIterative(root)) // Output: false
}
This iterative solution also runs in O(n) time complexity. The space complexity is O(n) in the worst case because the queue may hold up to n nodes.
Approach 3: Iterative Solution Using a Stack
Alternatively, we can use a stack instead of a queue to perform a depth-first comparison. The logic is nearly identical to the queue-based approach, but the order of processing changes because a stack follows last-in-first-out behavior.
package main
import "fmt"
type TreeNode struct {
Val int
Left *TreeNode
Right *TreeNode
}
// isSymmetricStack uses a stack to check symmetry iteratively.
func isSymmetricStack(root *TreeNode) bool {
if root == nil {
return true
}
stack := []*TreeNode{root.Left, root.Right}
for len(stack) > 0 {
n1 := stack[len(stack)-1]
stack = stack[:len(stack)-1]
n2 := stack[len(stack)-1]
stack = stack[:len(stack)-1]
if n1 == nil && n2 == nil {
continue
}
if n1 == nil || n2 == nil {
return false
}
if n1.Val != n2.Val {
return false
}
stack = append(stack, n1.Left, n2.Right)
stack = append(stack, n1.Right, n2.Left)
}
return true
}
func main() {
root := &TreeNode{Val: 1}
root.Left = &TreeNode{Val: 2}
root.Right = &TreeNode{Val: 2}
root.Left.Left = &TreeNode{Val: 3}
root.Right.Right = &TreeNode{Val: 3}
fmt.Println("Is symmetric:", isSymmetricStack(root)) // Output: true
}
Testing Your Solution
Writing comprehensive tests is essential to ensure your solution handles all edge cases. Go has a built-in testing framework that makes this straightforward. Here is an example test file:
package main
import "testing"
func TestIsSymmetric(t *testing.T) {
tests := []struct {
name string
tree *TreeNode
expected bool
}{
{
name: "empty tree",
tree: nil,
expected: true,
},
{
name: "single node",
tree: &TreeNode{Val: 1},
expected: true,
},
{
name: "symmetric tree",
tree: &TreeNode{
Val: 1,
Left: &TreeNode{
Val: 2,
Left: &TreeNode{Val: 3},
Right: &TreeNode{Val: 4},
},
Right: &TreeNode{
Val: 2,
Left: &TreeNode{Val: 4},
Right: &TreeNode{Val: 3},
},
},
expected: true,
},
{
name: "asymmetric tree",
tree: &TreeNode{
Val: 1,
Left: &TreeNode{
Val: 2,
Right: &TreeNode{Val: 3},
},
Right: &TreeNode{
Val: 2,
Right: &TreeNode{Val: 3},
},
},
expected: false,
},
{
name: "values differ",
tree: &TreeNode{
Val: 1,
Left: &TreeNode{Val: 2},
Right: &TreeNode{Val: 3},
},
expected: false,
},
}
for _, tt := range tests {
t.Run(tt.name, func(t *testing.T) {
result := isSymmetric(tt.tree)
if result != tt.expected {
t.Errorf("expected %v, got %v", tt.expected, result)
}
})
}
}
Run the tests with the following command:
go test -v
Best Practices
When solving the Symmetric Tree problem in Go, keep the following best practices in mind:
- Handle nil cases early: Always check for nil nodes at the beginning of your function to avoid nil pointer dereferences.
- Choose the right approach: Use recursion for readability and simplicity. Use iteration when dealing with potentially deep trees that could cause stack overflow.
- Write comprehensive tests: Cover edge cases such as empty trees, single-node trees, and trees with mismatched values.
- Optimize for clarity first: A clear, correct solution is more valuable than a prematurely optimized one. Optimize only after your solution works correctly.
- Understand the trade-offs: The recursive approach uses O(h) space on the call stack, while the iterative approach uses O(n) space for the queue or stack. Choose based on your constraints.
- Use meaningful variable names: Names like
n1andn2are acceptable, butleftNodeandrightNodemake your code more readable.
Common Pitfalls to Avoid
Even experienced developers can make mistakes when solving this problem. Here are some common pitfalls:
- Forgetting to check both structure and values: Two subtrees can have the same values but different structures. You must verify both.
- Incorrect child pairing: When comparing mirrors, the left child of one node must be compared with the right child of the other, not the left with the left.
- Ignoring the empty tree case: An empty tree is considered symmetric by definition. Make sure your solution returns true for a nil root.
- Mishandling nil children: If one node has a nil child and the other does not, the tree is not symmetric. Always check for this condition.
Performance Comparison
Let us compare the performance characteristics of the recursive and iterative approaches:
+-------------------+----------------+-----------------+
| Approach | Time Complexity| Space Complexity|
+-------------------+----------------+-----------------+
| Recursive | O(n) | O(h) |
| Iterative (Queue) | O(n) | O(n) |
| Iterative (Stack) | O(n) | O(n) |
+-------------------+----------------+-----------------+
In the table above, n represents the number of nodes and h represents the height of the tree. For a balanced tree, h is approximately log(n), making the recursive approach more memory efficient. For a skewed tree, h approaches n, and both approaches have similar space complexity.
Conclusion
The Symmetric Tree problem is an excellent exercise for strengthening your understanding of binary trees, recursion, and iterative traversal techniques. In this tutorial, we explored three different approaches to solve it in Go: a recursive solution, a queue-based iterative solution, and a stack-based iterative solution. Each approach has its own trade-offs in terms of readability and memory usage. By mastering these techniques and following best practices such as handling edge cases, writing comprehensive tests, and choosing the right approach for your constraints, you will be well-prepared to tackle this problem in interviews and real-world applications. Remember that the key to solving tree problems effectively is to think recursively first, then translate that logic into an iterative solution when necessary.