Problem: Please implement a function which returns mirror of a binary tree.
Binary tree nodes are defined as:
Analysis: Mirror of binary trees may be a new concept for many candidates, so they may not find a solution in short time during interviews. In order to get some visual ideas about mirrors, we may draw a binary tree and its mirror according to our daily experience. For example, the binary tree on the right of Figure 1 is the mirror of the left one.
|Figure 1: Two binary trees which are mirrors of each other|
Let us analyze these two trees in Figure 1 carefully to get the steps of mirrors. Their root nodes are identical, but their left and right children are swapped. Firstly we may swap two nodes under the root of the original binary tree, and it becomes the second tree in Figure 2.
Figure 2: Process to get mirror of a binary tree. (a) Swap children of the root node; (b) Swap children of the node 10; (c) Swap the children of node 6.
Now we can summarize the process for mirror: We visit all nodes in a binary tree with pre-order traversal, and swap the children of current visited node if it has. We will get mirror of a binary tree after we visit all of its nodes.
Let us begin to write code after we get clear ideas about the process. The following is the sample code:
void Mirror(BinaryTreeNode *pNode)
if((pNode == NULL) || (pNode->m_pLeft == NULL && pNode->m_pRight))
BinaryTreeNode *pTemp = pNode->m_pLeft;
pNode->m_pLeft = pNode->m_pRight;
pNode->m_pRight = pTemp;
The discussion about this problem is included in my book <Coding Interviews: Questions, Analysis & Solutions>, with some revisions. You may find the details of this book on Amazon.com, or Apress.
The author Harry He owns all the rights of this post. If you are going to use part of or the whole of this ariticle in your blog or webpages, please add a referenced to http://codercareer.blogspot.com/. If you are going to use it in your books, please contact me (firstname.lastname@example.org) . Thanks.