Mirror binary search tree
Mirror Binary Search Tree means, left child of each node becomes right child and vice-a-versa. Resultant tree be a tree which will be seen in mirror image of given BST. To understand basics about binary search tree, please refer : insert in BST, search in BST
Algorithm to mirror binary search tree
There are two approaches to this problem. First is to swap data of left and right child of each node. In this approach, it is mandatory to solve this problem bottom up because we must swap children nodes before parent node is swapped with it’s sibling.
Another approach is to swap the pointers themselves. That mean left pointer now start pointing to right child and right pointer to left child. Here, there is no strict requirement that you need to mirror children before parent node, because pointers themselves are swapped and left and right will anyway be pointing to entire right and left subtree children respectively. Even if you change left child of node to right child, entire left sub tree below the node will become right subtree of node. However, in my honest opinion, follow post order approach, which is to mirror children first and then parent node.
And their comes the solution. Process child nodes first and then the parent node. Typical postorder solution. Only change is print statement in post order traversal will be replaced by swapping of nodes.
To mirror a BST, we need to again start from the leaves. We first swap the lower most nodes, then move up till the root.
1. Start with root node. 2. If root is null return. 3. If there is left child, then mirror the left subtree 4. If there is right child, then mirror the right sub tree. 5. Swap left and right child.
Mirror binary search tree implementation
Complexity of recursive implementation to mirror a binary search tree is O(n) as each node of tree is traversed at least once.
Please share if something is wrong or missing. Sharing is caring. If you are interested in contributing to website, please contact us.