Invert Binary Tree
Understand and solve the interview question "Invert Binary Tree".
We'll cover the following...
Description
In this lesson, your task is to invert a given a binary tree, T
.
Let’s look at an example below:
Coding exercise
main.py
TreeNode.py
from TreeNode import *def invert_tree(root):pass
Invert binary tree
Solution
We can solve this problem using depth-first search (DFS).
The inverse of an empty tree is the empty tree. To invert tree T
with root
and subtrees left
and right
, we keep root the same and invert the right
and left
subtrees.
Let’s review the implementation below:
main.py
TreeNode.py
from TreeNode import *def invert_tree(root):if root is None:return rootright = invert_tree(root.right);left = invert_tree(root.left);root.left = right;root.right = left;return root;# Driver Coderoot = TreeNode(1)root.left = TreeNode(2)root.right = TreeNode(3)root.left.left = TreeNode(4)root.left.right = TreeNode(5)root.right.left = TreeNode(6)root.right.right = TreeNode(7)print_tree(invert_tree(root))
Invert binary tree
Complexity measures
Time Complexity | Space Complexity |
---|