226: Invert Binary Tree#
Difficulty: Easy
Link to Problem: To see the Invert Binary Tree problem on LeetCode, click here!
Given the root of a binary tree, invert the tree, and return its root.
Constraints:
The number of nodes in the tree is in the range
[0, 100]
.-100 <= Node.val <= 100
# Definition for a binary tree node.
class TreeNode:
def __init__(self, val=0, left=None, right=None):
self.val = val
self.left = left
self.right = right
def invertTree(root):
# Base case: If the root is None or the tree is empty, return None.
if not root:
return None
# Swap the left and right subtrees of the current node.
root.left, root.right = root.right, root.left
# Recursively invert the left and right subtrees.
invertTree(root.left)
invertTree(root.right)
return root
Explanation:#
We start by defining a TreeNode class, which represents a node in a binary tree. Each node has a value (
val
), a left child (left
), and a right child (right
).The
invertTree
function is defined to invert the binary tree. It takes the root node of the tree as an argument.In the
invertTree
function, we have a base case to handle the scenario when the root isNone
(empty tree). In such cases, we returnNone
because there’s nothing to invert.For non-empty trees, we swap the left and right subtrees of the current node. This effectively inverts the tree at the current node.
We then recursively call
invertTree
on the left and right subtrees to invert them.Finally, we return the root of the inverted tree.
Test cases#
### Example 1
# Input: root = [4,2,7,1,3,6,9]
root1 = TreeNode(4)
root1.left = TreeNode(2)
root1.right = TreeNode(7)
root1.left.left = TreeNode(1)
root1.left.right = TreeNode(3)
root1.right.left = TreeNode(6)
root1.right.right = TreeNode(9)
inverted_root1 = invertTree(root1)
print("Inverted Tree (Example 1):", inverted_root1)
Inverted Tree (Example 1): <__main__.TreeNode object at 0x7f30502756c0>
### Example 2
# Input: root = [2,1,3]
root2 = TreeNode(2)
root2.left = TreeNode(1)
root2.right = TreeNode(3)
inverted_root2 = invertTree(root2)
print("Inverted Tree (Example 2):", inverted_root2)
Inverted Tree (Example 2): <__main__.TreeNode object at 0x7f30502751b0>
### Example 3
# Input: root = []
root3 = None # Empty tree
inverted_root3 = invertTree(root3)
print("Inverted Tree (Example 3):", inverted_root3)
Inverted Tree (Example 3): None
Let’s discuss the time and space complexity of the provided Python code to invert a binary tree.
Time Complexity:
The time complexity of the invertTree
function is
The reason for this time complexity is the depth-first traversal of the tree, where we recursively process the left and right subtrees of each node.
Space Complexity:
The space complexity of the code is determined by the function call stack during the recursion. In the worst case, the space complexity is
In a completely unbalanced binary tree (essentially a linked list), the height
In a balanced binary tree, such as a full binary tree, the height
The space complexity depends on how balanced the tree is. In practical scenarios, binary trees are often approximately balanced, so the space complexity is typically closer to
In summary:
Time Complexity:
where is the number of nodes.Space Complexity:
, where is the height of the binary tree. In the worst case, it can be , and in a balanced tree, it is .
Keep in mind that these complexities are based on the recursive implementation provided. Iterative solutions can achieve the same task with