Teaching Kids Programming: Videos on Data Structures and Algorithms
This problem was inspired by this original tweet by Max Howell:
Google: 90% of our engineers use the software you wrote (Homebrew), but you can’t invert a binary tree on a whiteboard so f*** off.Invert a binary tree.
Example:Input:
4 / \ 2 7 / \ / \ 1 3 6 9Output:
4 / \ 7 2 / \ / \ 9 6 3 1
Invert a Binary Tree by Recursive Algorithm
Recursion is a powerful tool and by using it, we can invert a binary tree in a trivial manner. The terminal case is to invert a None node which is None, then, we just have to recursively invert left and right subtrees, and assign the results to the right and left pointers.
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 | # 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 class Solution: def invertTree(self, root: TreeNode) -> TreeNode: if root is None: return None left = self.invertTree(root.left) right = self.invertTree(root.right) root.left = right root.right = left return root |
# 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 class Solution: def invertTree(self, root: TreeNode) -> TreeNode: if root is None: return None left = self.invertTree(root.left) right = self.invertTree(root.right) root.left = right root.right = left return root
The complexity is O(N) where N is the number of the nodes in the binary tree. Using recursion gives O(N) space usage.
See also other posts on inverting the binary tree:
- Teaching Kids Programming – Recursive Algorithm to Invert a Binary Tree
- How to Invert a Binary Tree in C/C++?
- Invert a Binary Tree using GoLang
–EOF (The Ultimate Computing & Technology Blog) —
loading...
Last Post: Algorithms to Count the Equivalent Pairs in an Array
Next Post: Depth First Search Algorithm to Perform Phone Number Permutations