Amazon Interview Question
Software Engineer / DevelopersCountry: United States
Interview Type: In-Person
void mirrorTree(TreeNode root){
//
if(root == null)
return;
mirrorTree(root._leftChild);
mirrorTree(root._rightChild);
if(root._leftChild!=null){
root._leftChild._rightChild = root;
root._leftChild = null;
}
if(root._rightChild!=null){
root._rightChild._leftChild = root;
root._rightChild = null;
}
}
public void createMirror(Node Root)
{
if(Root == null)
return;
Node L = Root.Left;
Node R= Root.Right;
Root.Left=R;
Root.Right=L;
CreateMirror(Root.Left);
CreateMirror(Root.Right);
}
oops my bad
public void createMirror(Node Root)
{
if(Root == null)
return;
CreateMirror(Root.Left);
CreateMirror(Root.Right);
Node L = Root.Left;
Node R= Root.Right;
Root.Left=R;
Root.Right=L;
}
well both iterations solve the purpose. the only question perhaps i didn't address is perhaps the requirement is to create a new tree instead of making the change in place
if both iterations solve the purpose, why did you say "oops my bad" and change it? idiot.
you should swap in the post order fashion and not the preorder one.
- Anonymous on September 22, 2013
oops my bad
public void createMirror(Node Root)
<snip, Rohit makes useless change>
- Rohit on September 22, 2013
Rohit = non-noob
public void mirror(Node originalTree, Node newTree)
{
if(originalTree== null)
return;
Node left = OriginalTree -> right;
Node right= OriginalTree -> left;
newTree = (Node) malloc (Node*sizeof(Node));
newTree->value = originalTree->value;
newTree->left = null;
newTree->right = null;
mirror(left, newTree -> left);
mirror(right, newTree -> right);
}
public TreeNode mirrorTree(TreeNode origTree)
{
if(NULL == origTree)
return NULL;
Node node = new TreeNode();
node->value = origTree->value;
node->left = mirrorTree(origTree->left);
node->right = mirrorTree(origTree->right);
return newTree;
}
void TreeOperation::mirrorTree(TreeNode* node){
if(node != NULL){
mirrorTree(node->getLeftChild());
mirrorTree(node->rightChild);
swapChildren(node);
}
}
void TreeOperation::swapChildren(TreeNode* parent){
TreeNode* temp;
temp=parent->getLeftChild();
parent->setLeftChild(parent->rightChild);
parent->rightChild = temp;
}
Please let me know If I am wrong
private TreeNode createMirror(TreeNode oldTree, TreeNode newTree){
if(oldTree == null || newTree == null){return null;}
newTree.left = oldTree.right;
newTree.right = oldTree.left;
createMirror(oldTree.left, newTree.right);
createMirror(oldTree.right, newTree.left);
}
public TreeNode createMirror(TreeNode oldTree){
if(oldTree == null){return null;}
TreeNode newTree = oldTree;
return createMirror(oldTree, newTree);
}
- Vir Pratap Uttam May 04, 2015