Problem #1 Solution

Google Easy-Medium

This is a classic recursion problem. We can identify these types by going over a few example cases by hand. This is typically a useful practice to get into regardless since it can help with debugging and solving edge cases.

This is marked as a Medium Problem. In practice, it is around the low end of medium. Problems such as this require an understanding of the data structure/process to solve.

By viewing a few examples, we can see the process is essentially swapping left and right nodes. Examining binary trees themselves, we see that they are symmetric. There is no difference between the implementation of the right node and the left node. Binary Tree Nodes are defined as:

Node(val, Node Left, Node Right), where Node can be either a Node or a None. This self-referential implementation is why recursion works so well for Trees.

Getting back to the problem. How can we invert the tree? Simple, swap the two children of a node and then swap the node with its Sibling. Work through it with pen and paper and small examples to convince yourselves it works.

Code:

def invert(node):

    if not node:

       return node

    left = invert(node.left)

    right = invert(node.right)

    node.left, node.right = right, left

    return node

Closing:

This problem is not very hard when you realize the trick. A lot of the easier Medium problems are that way. If you have any questions about it, feel free to let me know