Invert Binary


Invert a binary tree.
Example:
Input:
     4
   /   \
  2     7
 / \   / \
1   3 6   9
Output:
     4
   /   \
  7     2
 / \   / \
9   6 3   1
Trivia:
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.

I hope, you understand the above problem where we need to just invert the complete binary tree. While analyzing the problem, I found that we need some kind of storage where we can push elements using FIFO- First In First Out approach. We can say that it can be achieved using the queue data structure. We will push the root in the queue and iterate until the queue becomes empty. We poll/pop the node from the queue and swap it's left and right child and again push the left and right child into the queue itself. This process will happen until the queue is empty.

Note: We are not going to push the node which is null.
class TreeNode {
    int val;
    TreeNode left;
    TreeNode right;
    TreeNode() {
    }
    TreeNode(int val) {
        this.val = val;
    }
    TreeNode(int val, TreeNode left, TreeNode right) {
        this.val = val;
        this.left = left;
        this.right = right;
    }
}

public TreeNode invertTree(TreeNode root) {
    if (root == null || (root.left == null && root.right == null))
        return root;
    Queue<TreeNode> queue = new LinkedList<>();
    queue.add(root);
    while (!queue.isEmpty()) {
        TreeNode node = queue.poll();
        TreeNode left = node.left;
        node.left = node.right;
        node.right = left;
        if (node.left != null) {
            queue.add(node.left);
        }
        if (node.right != null) {
            queue.add(node.right);
        }
    }
    return root;
}
I hope you are understanding the solution to the given problem. We will come up with a new challenge soon.

Comments

Popular posts from this blog

Recursion

Stack

Data Structure & Algorithm