Inversion of Binary Tree in Java - Using Recursion

In this post, we will invert a given binary tree using recursion.

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

 Lets create the class for Node, that can be used to construct a Binary Tree

class TreeNode{
    private TreeNode left;
    private TreeNode right;
    private String value;
    public TreeNode(String value){ this.value = value; }
    public TreeNode(TreeNode left, TreeNode right, String value){
        this.left = left;
        this.right = right;
        this.value = value;
    }
    public TreeNode getLeft() { return left; }
    public void setLeft(TreeNode left) { this.left = left; }
    public TreeNode getRight() { return right; }
    public void setRight(TreeNode right) { this.right = right; }
    public String getValue() { return value; }
    public void setValue(String value) { this.value = value; }
}

Now, we will prepare a binary tree like this:

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;
}

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.

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;
}

In the above 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.

You can find the whole code here. Github Link

Also, you can find the Binary Tree - Traversal post here.

Please comment down your suggestions.