#LC226 - Inversion Of Binary Tree Using Recursion

Following the last post on the binary tree traversals, in this post we will try to invert a given binary tree.

Binary tree is a data structure in which a node can have maximum two child nodes and minimum zero nodes. Each node contains the value of the node, the left node reference and right node reference.

     4
   /   \
  2     7
 / \   / \
1   3 6   9

In the above binary tree, root node has a value of 4 and 2 is the left node of the root and 7 is right node of the root. An inverted node will look like this, where the left node is swapped with the right node.

     4
   /   \
  7     2
 / \   / \
9   6 3   1

Create the Node

Node can be used to construct a Binary Tree. We will be using the lombok library to avoid the boilerplate code. Using @Data annotation, we can avoid writing the constructors, setters and getters method.

@Data
class TreeNode{
    private TreeNode left;
    private TreeNode right;
    private String value;  
}

Prepare a binary tree

public TreeNode prepareBTree(){
    TreeNode leaf1 = new TreeNode("1");
    TreeNode leaf2 = new TreeNode("3");
    TreeNode leaf3 = new TreeNode("6");
    TreeNode leaf4 = new TreeNode("9");

    TreeNode nodeRight = new TreeNode(leaf3, leaf4, "7");
    TreeNode nodeLeft = new TreeNode(leaf1, leaf2, "2");

    TreeNode root = new TreeNode(nodeLeft, nodeRight, "4");
    return root;
}

Invert Binary Tree (Algorithm/Logic)

To invert the binary tree, we will use recursion and use the same logic we use for swapping two values. Using a third Node, we will swap the left and right nodes with each other.

In the below method, we are recursively going to each sub-binary tree and swapping the left node and right node with each other. Here the exit criteria will be leaf node. Leaf nodes don't have any left or right node. So, if a node.left is null or node.right is null, then the program will return the null.

public TreeNode invertBTree(TreeNode node){
    if(null==node){
        return null;
    }
    if(null==node.getLeft() && null==node.getRight()){
        return node;
    }
    TreeNode temp = node.getLeft();
    node.setLeft(node.getRight());
    node.setRight(temp);

    invertBTree(node.getLeft());
    invertBTree(node.getRight());
    return node;
}

You can find the whole code here. Github Link

Please do suggest more content topics of your choice and share your feedback. Also subscribe and appreciate the blog if you like it.