Interview Practice 15 - Mirror Image of Binary Tree

Question

Construct 2 algorithms to make mirror image of any binary tree inputs, one of them using recursive method, another one using looping method. Mirror image means a binary tree that is the horizontal reflection of the original tree.

Solution

First, to do it in recursive method, we can perform pre-order traversal as usual, see preference. Then swap the left and right children for every node.

reflect(node) if node is null then return swap(node.left, node.right) if node.left is not null then reflect(node.left) if node.right is not null then reflect(node.right)

Second, to do it in looping method, we can make use of a stack. Put root node in the stack first. Then in a while-loop, as long as the stack isn’t empty, swap its children. Then put the children nodes into the stack.

reflect(root) if root is null then return stack.push(root) while stack is not empty, do node = stack.pop() swap(node.left, node.right) if node.left is not null then reflect(node.left) if node.right is not null then reflect(node.right)

Example

node structure class bst_node: value = None left = None right = None def init(self, value, left=None, right=None): self.value = value self.left = left self.right = right # swap node's children while visiting def visit(node): temp = node.left node.left = node.right node.right = temp # reflect a binary tree def depth_first_traversal(node): if not node: return visit(node) if node.left: depth_first_traversal(node.left) if node.right: depth_first_traversal(node.right) # debug function to print tree def print_tree(node, indent=''): print "%s-%s" % (indent, node.value) if node.left: print_tree(node.left, indent + ' ') if node.right: print_tree(node.right, indent + ' ') # a binary tree and display how was it before reflection node_05 = bst_node(5) node_07 = bst_node(7) node_09 = bst_node(9) node_11 = bst_node(11) node_06 = bst_node(6, node_05, node_07) node_10 = bst_node(10, node_09, node_11) node_08 = bst_node(8, node_06, node_10) root = node_08 print_tree(root) # do reflection depth_first_traversal(root) print_tree(root)

node structure class bst_node: value = None left = None right = None def init(self, value, left=None, right=None): self.value = value self.left = left self.right = right # what to do in a loop, here swap the children def visit(node): temp = node.left node.left = node.right node.right = temp # reflect a binary tree def depth_first_traversal(root): if not root: return stack = [root] while len(stack) > 0: node = stack.pop() visit(node) if node.left: stack.append(node.left) if node.right: stack.append(node.right) # debug function to print tree def print_tree(node, indent=''): print "%s-%s" % (indent, node.value) if node.left: print_tree(node.left, indent + ' ') if node.right: print_tree(node.right, indent + ' ') # a binary tree and display how was it before reflection node_05 = bst_node(5) node_07 = bst_node(7) node_09 = bst_node(9) node_11 = bst_node(11) node_06 = bst_node(6, node_05, node_07) node_10 = bst_node(10, node_09, node_11) node_08 = bst_node(8, node_06, node_10) root = node_08 print_tree(root) # do reflection depth_first_traversal(root) print_tree(root)

struct BSTreeNode // a node in the binary search tree (BST) { int m_nValue; // value of node BSTreeNode *m_pLeft; // left child of node BSTreeNode *m_pRight; // right child of node }; //就是递归翻转树,有子树则递归翻转子树。 //July、2010/10/19 void Revertsetree(list *root) { if(!root) return; list *p; p=root->leftch; root->leftch=root->rightch; root->rightch=p; if(root->leftch) Revertsetree(root->leftch); if(root->rightch) Revertsetree(root->rightch); }

void Revertsetree(list phead) { if(!phead) return; stack<list> stacklist; stacklist.push(phead); //首先把树的头结点放入栈中。 while(stacklist.size()) //在循环中,只要栈不为空,弹出栈的栈顶结点,交换它的左右子树 { list* pnode=stacklist.top(); stacklist.pop(); list *ptemp; ptemp=pnode->leftch; pnode->leftch=pnode->rightch; pnode->rightch=ptemp; if(pnode->leftch) stacklist.push(pnode->leftch); //若有左子树,把它的左子树压入栈中 if(pnode->rightch) stacklist.push(pnode->rightch); //若有右子树,把它的右子树压入栈中 } }

Reference

Pre-order Tree Transversal (Wikipedia)

Show Comments