226. Invert Binary Tree — LeetCode(Python)
I got you!
Problem:
Given the root of a binary tree, invert the tree, and return its root.
Example 1:
Input: root = [4,2,7,1,3,6,9]
Output: [4,7,2,9,6,3,1]Example 2:
Input: root = [2,1,3]
Output: [2,3,1]Example 3:
Input: root = []
Output: []Constraints:
- The number of nodes in the tree is in the range
[0, 100]. -100 <= Node.val <= 100
Solution:
1. Recursive —
Explanation —
We can easily solve this problem recursively.
The base case of the recursion would be when we reach a NULL node, in which case we return from the function without doing anything.
We start by swapping the left and right children of root.
Next, we call our function recursively on the left and right subtrees to do the same for them.
Recursion takes care of the rest as at every call, we are performing the same function — swapping the left and right children of a node.
Finally, we return the root of the inverted binary tree.
Time and Space Complexity —
Since we are visiting every node in the tree a constant number of times, we can say that our algorithm requires linear amount of time to run.
Also, the recursion stack could be storing all nodes in the tree in case of a really skewed tree (like a linked list). So, we assume the space complexity to be linear in the worst case.
Thus, if n is the number of nodes in the tree.
Time Complexity: O(n)
Space Complexity: O(n)
2. Iterative —
Explanation —
We can use a stack to imitate the recursion from the previous solution in our iterative solution.
Initially, the stack holds only the root.
We perform the following functions until the stack is non-empty —
- pop an element from the stack
- if it is a non-NULL node, append it’s left and right children to the stack
- swap the left and right children
Finally, we return the root of the inverted tree when the while loop terminates, which means all nodes in the tree have been traversed.
Time and Space Complexity —
Since we are visiting all nodes in the tree a constant number of times, we can say that our algorithm requires a linear amount of time to run.
Also, the maximum number of nodes that the stack could be storing at a given point is a function of the number of nodes in the tree. So, we can say that the amount of auxiliary space required is also linear.
Thus, if n is the number of nodes in the given binary tree,
Time Complexity: O(n)
Space Complexity: O(n)
