🧩 Problem Statement
Given the root of a binary tree, invert the tree, meaning that you swap the left and right subtrees at every node.
Implement the function:
go
func invertTree(root *TreeNode) *TreeNode
📘 Example
go
Input:
[4, 2, 7, 1, 3, 6, 9]
Output:
[4, 7, 2, 9, 6, 3, 1]
📝 Explanation:
The binary tree is:
markdown
4
/ \
2 7
/ \ / \
1 3 6 9
After inverting, it becomes:
markdown
4
/ \
7 2
/ \ / \
9 6 3 1
🧠 Approach
We need to invert the binary tree by swapping the left and right children of every node.
Plan:
- Base case: If the root is
nil, return nil. This handles empty trees.
- Recursive case: Swap the left and right children of the current node.
- Perform this operation recursively on the left and right subtrees.
We can perform this inversion either using a Depth-First Search (DFS) or a Breadth-First Search (BFS). In this solution, we'll use DFS with recursion.
✅ Go Implementation
go
package main
import "fmt"
// TreeNode defines the structure of a binary tree node
type TreeNode struct {
Val int
Left *TreeNode
Right *TreeNode
}
// Invert the binary tree recursively
func invertTree(root *TreeNode) *TreeNode {
// Base case: if the node is nil, return nil
if root == nil {
return nil
}
// Swap the left and right children
root.Left, root.Right = root.Right, root.Left
// Recursively invert the left and right subtrees
invertTree(root.Left)
invertTree(root.Right)
return root
}
// Helper function to create a new TreeNode
func createNode(val int) *TreeNode {
return &TreeNode{Val: val}
}
// Helper function to print the tree in Pre-order traversal
func printTree(root *TreeNode) {
if root == nil {
return
}
fmt.Print(root.Val, " ")
printTree(root.Left)
printTree(root.Right)
}
func main() {
// Example usage
// Create the tree: 4
// / \
// 2 7
// / \ / \
// 1 3 6 9
root := createNode(4)
root.Left = createNode(2)
root.Right = createNode(7)
root.Left.Left = createNode(1)
root.Left.Right = createNode(3)
root.Right.Left = createNode(6)
root.Right.Right = createNode(9)
// Invert the tree
invertedRoot := invertTree(root)
// Print the inverted tree in Pre-order traversal
printTree(invertedRoot) // Output: 4 7 9 6 2 3 1
}
📦 Example Usage
go
func main() {
// Create the tree: 4
// / \
// 2 7
// / \ / \
// 1 3 6 9
root := createNode(4)
root.Left = createNode(2)
root.Right = createNode(7)
root.Left.Left = createNode(1)
root.Left.Right = createNode(3)
root.Right.Left = createNode(6)
root.Right.Right = createNode(9)
// Invert the tree
invertedRoot := invertTree(root)
// Print the inverted tree in Pre-order traversal
printTree(invertedRoot) // Output: 4 7 9 6 2 3 1
}
⏱️ Time & Space Complexity
- Time Complexity:
- O(n), where
n is the number of nodes in the tree. We visit each node once in a depth-first manner.
- Space Complexity:
- O(h), where
h is the height of the tree. This is the space required for the recursion stack. In the worst case, the tree can be a straight line (degenerate tree), where the space complexity will be O(n), and in the best case (balanced tree), it will be O(log n).
This solution efficiently inverts the binary tree using a depth-first search (DFS) approach with recursion.