Amazon Interview Question Software Engineer / Developers
0of 0 votesMirror of Binary tree without recursion.
I suppose the question demands the interviewee to "create" a mirror tree, not "print" a mirror tree.
can we do like this?
as we print binary tree in level order (BFS)
similarly , we will insert root into one queue . Then we insert one gap node (as differentiator for next level) .. now we create a new tree with this root node ..
as we inserted in queue , lets dequeue it and enqueue its right and left in queue and then one gap node... then dequeue .. (left node) .. insert the value of this left in newly created tree .. then enqueue the left and right of this deque'ed node into queue. Then dequeue another node .. follow same process.. as the next dequeue is gap node , again enqueue one gap node ..
Like this can we create mirror image with out recurssion.
Please correct me if I am wrong
Isn't it a variant of pre-order traversal? You traverse root first, then, right-branch first, and then left-branch.
I used 2 stacks.. Pushed left subtree contents to 1 stack and right subtree contents to 2nd stack.. and then popped contents of each stack to the opposite subtrees. But after interview realised, there s a shorter method by using just 1 stack
// Mirror of binary tree without recursion is done
// using a stack and then basically do a DFS
void MirrorWithoutRecursion(Node * tree)
{
if (!tree)
return;
Stack s;
s.push(tree);
while(!s.empty())
{
Node * current = s.pop();
// Swap the children
//
Node * temp = current->right;
current->right = current->left;
current->left = temp;
// Push the children on the stack
//
if (current->right)
s.push(current->right);
if (current->left)
s.push(current->left);
}
}
@coolcoder:
Solution to this problem depends upon whether the interviewer wants the input tree to be modified.
If input can be modified then yours is efficient solution.
But if input cannot be modified then solution given by Anonymous is good.
I'm not sure if this will retain the structure. Basically its like doing an inorder traversal, which in itself doesn't preserve complete information. I think you need to push those NULL entries as well, and check while popping.
Here's my code (mirrorLR function, ignore the rest if you don't want to run it):
#include <stdio.h>
struct snode {
void *data;
struct snode *next;
};
struct snode *newSNode(void *data, struct snode *next) {
struct snode *node = (struct snode *) malloc(sizeof(struct snode));
node->data = data;
node->next = next;
return node;
}
typedef struct {
struct snode *top;
} Stack;
Stack *newStack() {
Stack *s = (Stack *) malloc(sizeof(Stack));
s->top = NULL;
return s;
}
void *pop(Stack *s) {
struct snode *node = s->top;
void *data;
if(node == NULL)
return NULL;
s->top = node->next;
data = node->data;
free(node);
return data;
}
void push(Stack *s, void *data) {
struct snode *node = newSNode(data, s->top);
s->top = node;
}
int isEmpty(Stack *s) {
return (s->top == NULL);
}
struct tnode {
int data;
struct tnode *left, *right;
};
struct tnode *newTNode(int data, struct tnode *left, struct tnode *right) {
struct tnode *node = (struct tnode *) malloc(sizeof(struct tnode));
node->data = data;
node->left = left;
node->right = right;
return node;
}
typedef struct {
struct tnode *root;
} Tree;
Tree *newTree() {
Tree *t = (Tree *) malloc(sizeof(Tree));
t->root = NULL;
return t;
}
void inorder(struct tnode *node) {
if(node == NULL)
return;
printf("%d\n", node->data);
inorder(node->left);
inorder(node->right);
}
void preorder(struct tnode *node) {
if(node == NULL)
return;
preorder(node->left);
printf("%d\n", node->data);
preorder(node->right);
}
Tree *buildTree() {
Tree *t = newTree();
t->root = newTNode(1, NULL, NULL);
t->root->left = newTNode(2, NULL, NULL);
t->root->right = newTNode(8, NULL, NULL);
t->root->left->left = newTNode(3, NULL, NULL);
t->root->left->right = newTNode(6, NULL, NULL);
t->root->left->left->left = newTNode(4, NULL, NULL);
t->root->left->left->right = newTNode(5, NULL, NULL);
t->root->left->right->right = newTNode(7, NULL, NULL);
t->root->right->right = newTNode(9, NULL, NULL);
t->root->right->right->left = newTNode(10, NULL, NULL);
t->root->right->right->right = newTNode(11, NULL, NULL);
return t;
}
// Mirror the tree using stack
void mirrorLR(Tree *t) {
struct tnode *node, *temp;
Stack *s = newStack();
push(s, t->root);
while(!isEmpty(s)) {
node = pop(s);
if(node == NULL)
continue;
temp = node->left;
node->left = node->right;
node->right = temp;
push(s, node->left);
push(s, node->right);
}
}
int main() {
Tree *t1 = buildTree();
Tree *t2 = newTree();
mirrorLR(t1);
printf("Inorder Traversal\n");
inorder(t1->root);
printf("Preorder Traversal\n");
preorder(t1->root);
return 0;
}
Output:
Inorder Traversal
1
8
9
11
10
2
6
7
3
5
4
Preorder Traversal
11
9
10
8
1
7
6
2
5
3
4
Anything we can do with recursion can be done without recursion using STACK
1. Push the node in the stack
2. Pop node from the stack and swap its left and right child
3. Push the right child followed by the left.
4. continue steps 1 to 3 till the stack is empty
1
2 3
4 5 6 7
stack: 1
pop 1: swap 2 and 3. Push 2 and 3 into the stack
stack: 2 3
pop 2: swap 4 and 5. Push 4 and 5 into the stack
stack: 4 5 3
pop 4: no children return
stack: 5 3
pop 5: no children return
stack: 3
pop 3: swap 6 and 7. Push 6 and 7 into the stack
stack: 6 7
pop 6: no children return
stack: 7
pop 7: no children return
o/p-->
1
3 2
7 6 5 4
// if see parent of any node remains the same, only the orientation changes..
enum {LEFT, RIGHT, NOT_VALID}
struct item {
TreeNode* child;
TreeNode* parent;
int orientation;
};
TreeNode* mirrorTree(TreeNode* root)
{
queue <item> q;
if (root != NULL) q.push( item(root, NULL, NOT_VALID) );
while (!q.empty()) {
TreeNode* current = q.top().child;
TreeNode* parent = q.top().parent;
int orientation = q.top().orientation;
q.pop();
if (parent && orientation == LEFT)
parent->right = current;
else if (parent && orientation == RIGHT)
parent->left = current;
if (current->left) q.push( item(current->left, current, LEFT) );
if (current->right) q.push( item(current->right, current, RIGHT) );
}
return root;
}
// iterative code
TreeNode* mirror(TreeNode* root)
{
stack<TreeNode*> s;
TreeNode* current;
while (!s.empty())
{
TreeNode* current = s.top(); s.pop();
// swap the children
swap(current->left, current->right);
// push the children to stack
if (current->left != NULL) s.push(current->left);
if (current->right != NULL) s.push(current->right);
}
return root;
}
This can be solved with two queue to return a new Tree which is mirror of given tree.
use two queues say given_queue and new_queue:
G: given Tree
Make new Tree(R).
Add G to given_queue and R to new_queue
1) new_queue(0).value = given_queue(0).value
2) if(G.left not null)
new_queue(0).right = new Tree();
Add left tree ( given_queue(0).left) in given_queue and add right tree (new_queue(0).right) to new_queue.
3) if(G.right not null)
new_queue(0).left = new Tree();
Add right tree ( given_queue(0).right) in given_queue and add left tree (new_queue(0).left) to new_queue.
4) Remove new_queue(0) and given_queue(0)
Repeat Step 1 to 4 until given_queue size is greater then 0.
R is new Tree which is mirror of Given Tree.
Here is code in Java:
class BinTree {
int value;
BinTree left;
BinTree right;
}
public static BinTree iMirror(BinTree head)
{
if(head == null)
return null;
List<BinTree> Q1 = new ArrayList<BinTree>();
List<BinTree> Q2 = new ArrayList<BinTree>();
Q1.add(head);
BinTree t = new BinTree();
t.value = head.value;
Q2.add(t);
while(Q1.size() > 0)
{ Q2.get(0).value = Q1.get(0).value;
if(Q1.get(0).left != null)
{ Q2.get(0).right = new BinTree();
Q2.add(Q2.get(0).right);
Q1.add(Q1.get(0).left);
}
if(Q1.get(0).right != null)
{ Q2.get(0).left = new BinTree();
Q2.add(Q2.get(0).left);
Q1.add(Q1.get(0).right);
}
Q2.remove(0);
Q1.remove(0);
}
return t;
}
Inspired by @coolcoder 's solution. If we don't want destroy the old input tree, we can build a mirror version of new tree in the following way: with 2 stacks
public static TreeNode mirrorCopy(TreeNode root){
if(root == null){
return null;
}
Stack<TreeNode> stack = new Stack<TreeNode>();
Stack<TreeNode> newStack = new Stack<TreeNode>();
stack.push(root);
TreeNode newRoot = new TreeNode(root.val);
newStack.push(newRoot);
while( !stack.isEmpty() ){
TreeNode cur = stack.pop();
TreeNode newCur = newStack.pop();
if(cur.right != null){
stack.push(cur.right);
newCur.left = new TreeNode(cur.right.val);
newStack.push(newCur.left);
}
if(cur.left != null){
stack.push(cur.left);
newCur.right = new TreeNode(cur.left.val);
newStack.push(newCur.right);
}
}
return newRoot;
}
void Mirror(struct BinaryTree *root)
{
struct queue *Q = NULL;
struct BinaryTree *temp = NULL;
Q = enQueue(Q,root);
while(!isQueueEmpty(Q))
{
temp = Q->front->data;
printf("%d\t",temp->data);
Q = deQueue(Q);
if(temp->right)
{
Q = enQueue(Q,temp->right);
}
if(temp->left)
{
Q = enQueue(Q,temp->left);
}
}
free(Q);
}
void Mirror(struct BinaryTree *root)
{
struct queue *Q = NULL;
struct BinaryTree *temp = NULL;
Q = enQueue(Q,root);
while(!isQueueEmpty(Q))
{
temp = Q->front->data;
printf("%d\t",temp->data);
Q = deQueue(Q);
if(temp->right)
{
Q = enQueue(Q,temp->right);
}
if(temp->left)
{
Q = enQueue(Q,temp->left);
}
}
free(Q);
}
Please correct me if this is wrong.
Code:
void Mirror(struct BinaryTree *root)
{
struct queue *Q = NULL;
struct BinaryTree *temp = NULL;
Q = enQueue(Q,root);
while(!isQueueEmpty(Q))
{
temp = Q->front->data;
printf("%d\t",temp->data);
Q = deQueue(Q);
if(temp->right)
{
Q = enQueue(Q,temp->right);
}
if(temp->left)
{
Q = enQueue(Q,temp->left);
}
}
free(Q);
}
can we do like this?
- Anonymous December 08, 2010as we print binary tree in level order (BFS)
similarly , we will insert root into one queue . Then we insert one gap node (as differentiator for next level) .. now we create a new tree with this root node ..
as we inserted in queue , lets dequeue it and enqueue its right and left in queue and then one gap node... then dequeue .. (left node) .. insert the value of this left in newly created tree .. then enqueue the left and right of this deque'ed node into queue. Then dequeue another node .. follow same process.. as the next dequeue is gap node , again enqueue one gap node ..
Like this can we create mirror image with out recurssion.
Please correct me if I am wrong