Mirror binary search tree

In last post Delete binary search tree , we learned how to use traversals to solve problems on binary tree. Mirror binary search tree is another such problem which can be solved purely with one of the traversals of binary tree. What does it mean to mirror a binary tree?  It means to swap left and right subtree, left child of node becomes right child and right child becomes left child. This happens at every level. For example, for below binary tree,

mirror tree will be as below

Mirror binary search tree : Thoughts

As we can see that to mirror a tree, we have to first mirror it’s left and right subtree.  Mirror process will be same for subtrees will also be the same, hence perfect case for recursive implementation.

Idea is to start from root node, check if there are left and right child. If no, do nothing. If yes, then move down the left child and first mirror the left subtree. Then if there is right child, mirror the right subtree and then finally swap left and right child of the node. This is typical postorder processing, where left and right subtrees are processed before root node. Processing here is to swap left and right child of node.

When do we stop? When node is leaf node, with node left and right child.

Mirror binary search tree : Implementation

#include<stdio.h>
#include<stdlib.h>
#include<math.h>
 
struct node{
	int value;
	struct node *left;
	struct node *right;
};
typedef struct node Node;

void mirrorBST(Node * root){
	if(!root)
		return;
	
	mirrorBST(root->left);
	mirrorBST(root->right);
	
	Node * temp  = root->right;
	root->right  = root->left ;
	root->left   = temp;
}

void inoderTraversal(Node * root){
	if(!root)
		return;
	
	inoderTraversal(root->left);
	printf("%d ", root->value);
	inoderTraversal(root->right);
}
Node *createNode(int value){
	Node * newNode =  (Node *)malloc(sizeof(Node));
	newNode->value = value;
	newNode->right= NULL;
	newNode->left = NULL;
	
	return newNode;
}
Node *addNode(Node *node, int value){
	if(node == NULL){
		return createNode(value);
	}
	else{
		if (node->value > value){
			node->left = addNode(node->left, value);
		}
		else{
			node->right = addNode(node->right, value);
		}
	}
	return node;
}

/* Driver program for the function written above */
int main(){
	Node *root = NULL;
	//Creating a binary tree
	root = addNode(root,30);
	root = addNode(root,20);
	root = addNode(root,15);
	root = addNode(root,25);
	root = addNode(root,40);
	root = addNode(root,37);
	root = addNode(root,45);
	
	mirrorBST(root);

	inoderTraversal(root);	
	return 0;
}

Java implementation

package com.company.BST;

import java.util.ArrayList;

/**
 * Created by sangar on 10.5.18.
 */
public class BinarySearchTree {

    private Node root;

    public void BinarySearchTree(){
        root = null;
    }

    public class Node {
        private int value;
        private  Node left;
        private Node right;

        public Node(int value) {
            this.value = value;
            this.left = null;
            this.right = null;
        }
    }

    public void insert(int value){
        this.root =  insertNode(this.root, value);
    }

    private Node insertNode(Node root, int value){
        if(root == null){
            //if this node is root of tree
            root = new Node(value);
        }
        else{
            if(root.value > value){
                //If root is greater than value, node should be added to left subtree
                root.left = insertNode(root.left, value);
            }
            else{
                //If root is less than value, node should be added to right subtree
                root.right = insertNode(root.right, value);
            }
        }
        return root;
    }

    public void mirror(){
        mirrorRecusrive(this.root);
    }
    private void mirrorRecusrive(Node root){
        if(root == null) return;

        //mirror left subtree
        mirrorRecusrive(root.left);
        //mirror right subtree
        mirrorRecusrive(root.right);

        //swap left and right child
        Node temp = root.left;
        root.left = root.right;
        root.right = temp;
    }
}

Test class

package com.company.BST;

/**
 * Created by sangar on 10.5.18.
 */
public class BinarySearchTreeTests {
    public static void main (String[] args){
        BinarySearchTree binarySearchTree = new BinarySearchTree();

        binarySearchTree.insert(7);
        binarySearchTree.insert(8);
        binarySearchTree.insert(6);
        binarySearchTree.insert(9);
        binarySearchTree.insert(3);
        binarySearchTree.insert(4);

        binarySearchTree.mirror();
        binarySearchTree.inorderTraversal();
    }
}

Mirror binary search tree : example

Let’s take an example and see how function works. Below is the tree to mirror.

We start with node(10). As it has left and right subtree, we have to first mirror those subtrees before we can swap left and right child of node(10).

Move down to left subtree to node(5), problem is reduced to mirror tree rooted at node(5).

As node(5) has left child, move down to left child which is node(1).

This the special case, as node(1) is leaf node, there is no need to swap anything. It also means tree rooted at node(1) is already mirrored. We move up the tree at node(5). As it has right child, we move down the right subtree at node(6).

Again, node(6) is leaf node so subtree at node(6) is already mirrored.

At this point, left and right subtrees of node(5) are mirrored, so just swap left and right child.

Now, tree rooted at node(5) is mirrored. We move up the root which is node(10).

Since, node(10) has right subtree, we have to first mirror right subtree.

Again, node(19) has left and right subtrees, we move down the left subtree.

Node(17) is leaf node, it is already mirrored.

Move down the right subtree to node(21). It is leaf node hence, already mirrored.

Now, we have mirrored both left and right subtree, all we need to swap left and right child.

At node(10), both it’s subtrees are mirrored, swap left and right child.

Complexity of algorithm to mirror binary search tree is O(n) as we have to scan all nodes at least once.

Please share if there is something wrong or missing. If you want to contribute and share your knowledge with thousands of learners across world, please reach out to us at communications@algorithmsandme.com.