How do you invert a binary tree, and what does the result look like?
You swap the left and right child of every node. That is the whole thing.
class TreeNode:
def __init__(self, value, left=None, right=None):
self.value = value
self.left = left
self.right = right
def invert_tree(root):
if root is None:
return None
root.left, root.right = root.right, root.left
invert_tree(root.left)
invert_tree(root.right)
return root
So what does the result look like? It is the mirror image of the original tree. Every node that had a left child now has that child on the right, and every node that had a right child now has that child on the left.
the original the inverted
8 8
/ \ / \
3 10 10 3
/ \ \ / / \
1 6 14 14 6 1
And how does the code work? The line root.left, root.right = root.right, root.left swaps the two children in one line. Then you call the same function on both of the new children, and the same happens all the way down.
And the stopping condition is when the node is nothing. There is nothing to swap there, so the function gives back nothing.
And the complexity is O of n for the time, because every node is visited once, and O of h for the space because of the call stack.
And there is a detail worth knowing about. The swap line uses the form with two names on the left and two values on the right. Python works out all the values on the right first and then puts them in the names on the left, so the swap is safe. If you did it in two separate lines then the second line would put the old left child back and you would undo the first line.
# This does not work, because the second line undoes the first.
root.left = root.right
root.right = root.left
# This one works.
root.left, root.right = root.right, root.left
So the rule to remember is this. Swapping the two children at every node turns the tree into its mirror image.
The last question in this topic shows the version without recursion.