Invert Binary Tree

Queues based approach

We will be taking the help of a queue data structure in order to solve this problem. A queue has following properties.

• Insertion from the end (Called enque)
• Deletion from the start. (Called dequeue)

Also, A queue helps in implenting what is called a Breadth First Traversal - Which is a way of traversing a tree/graph in a Breadth first manner. i.e. , We first explore the same level of the tree (or the same breadth) and then move into deeper levels of the tree.

Simply put: neighbours first, children next.

1. Initialize a queue that contains only the tree value to start with (this is passed as an input parameter to the function).
2. While the queue is not empty,
   1. Remove the first element from the queue. (We will call this currentNode).
   2. Assign tree.left to the right subtree and tree.right to the left subtree. Essentially, we are trying to swap the left and right subtrees of the current node.
   3. If there is still a left subtree left, push it to the queue.
   4. If there is still a right subtree left, push it to the queue.
   5. Repeat step 2 untill the queue is empty.
3. Return result.

Time and Space Complexities

• O(N) Time complexity, because we check each element atmost once.
• O(N) Space complexity, because we can have a skewed tree. In average case it will be O(H) where H is the height of the tree.

Recursive approach

In the recursive approach, we try to swap the left and the right children as we traverse the tree top to down. Once we hit the base case, form there on the actuall swapping starts to happen.

1. If there is no tree, i.e. !tree - return. This will be the base case.
2. Recursively call the left subtree (call it left variable)
3. Recursively call the right subtree (call it right variable)
4. Assign left subtree to the right variable and right subtree to the left variable

tree.left = right;
tree.right = left;

What is happening is essentially we are travelling to the end of the tree, essentially trying to swap the end values first.

Since the end values are swapped by now, we move one level up (because of recursion, the function calls starts to pop off from the stack) and that is how the parents are swapped

Time and Space Complexities

• O(N) Time complexity, because we check each element atmost once.
• O(N) Space complexity, because we can have a skewed tree. In average case it will be O(H) where H is the height of the tree.

Another Recursive Approach - Swapping

As we saw earlier in the recursive approach, we essentially swapped children nodes of a parent node but we did it for the leaf nodes first. In this approach, we are going to start with the root node, and keep on swapping as and when we encounter left and right subtrees.

1. If there is no tree i.e. !tree - return. This will be our base case.
2. Swap the tree.left and tree.right values. (We are going to use a swap helper method here). Essentially, we are performing the swap as the first thing in the function.
3. Recursively call the function on the left subtree.
4. Recursively call the function on the right subtree.
5. Return tree at the end.

Time and Space Complexities

• O(N) Time complexity, because we check each element atmost once.
• O(N) Space complexity, because we can have a skewed tree. In average case it will be O(H) where H is the height of the tree.