Salesforce Interview Question
Developer Program EngineersCountry: India
Interview Type: Written Test
We can exploit a post-order traversal for our needs
public void mirror(Node n) {
if (n == null) { return; }
Node left = n.left;
Node right = n.right;
mirror(n.left);
mirror(n.right);
n.right = left;
n.left = right;
}
/* package whatever; // don't place package name! */
import java.util.*;
import java.lang.*;
import java.io.*;
/* Name of the class has to be "Main" only if the class is public. */
class Ideone
{
static class Node
{
char value;
Node left;
Node right;
Node(char val)
{
this.value = val;
this.left = null;
this.right = null;
}
}
public static void mirrorImage(Node root)
{
if(root == null)
return;
Node temp = root.right;
root.right = root.left;
root.left = temp;
mirrorImage(root.left);
mirrorImage(root.right);
}
public static void traversal(Node root)
{
if(root == null) return;
traversal(root.left);
System.out.print(" "+root.value);
traversal(root.right);
}
public static void main (String[] args) throws java.lang.Exception
{
// your code goes here
Node root = new Node('A');
Node B = new Node('B');
Node C = new Node('C');
root.left = B;
root.right = C;
traversal(root);
mirrorImage(root);
traversal(root);
}
}
Sample C Code:
void
swapNodes(Node *pTree) {
if(!pTree)
return;
Node *pTemp = pTree->pLeft;
pTree->pLeft = pTree->pRight;
pTree->pRight = pTemp;
}
Node*
mirror_tree(Node *pTree)
{
if(!pTree)
return NULL;
pTree->pLeft = mirror_tree(pTree->pLeft);
pTree->pRight = mirror_tree(pTree->pRight);
swapNodes(pTree);
return pTree;
}
int
main(int argc, char *argv[])
{
int choice = 0;
Node *pTree = NULL;
while((choice = menu())!= TREE_EXIT) {
switch(choice) {
case TREE_EXIT:
printf("Quitting\n");
break;
case TREE_INSERT:
printf("Entert the element \n");
scanf("%d", &key);
pTree = bst_insert(pTree, NULL, key, NULL);
printf(">%d\n", pTree->key);
break;
case TREE_MIRROR:
pTree = mirror_tree(pTree);
break;
default:
break;
}
}
}
void BinarySearchTree::Mirror(Node* node)
{
if (node == NULL)
{
return;
}
Node* temp = node->left;
node->left = node->right;
node->right = temp;
this->Mirror(node->left);
this->Mirror(node->right);
}
This problem tests your knowledge of recursion problems (e.g. stack overflow).
Naive solution via recursion will work, but in worst case will require O(n) additional memory (your tree is "a linked list" or in other words all node->right == NULL for all nodes in the tree)
Here is a solution which much more complicated, but work with O(1) addition memory and without recursion.
Actually this solution is finite state machine
void swap_branches(Node* node) {
Node* tmp;
tmp = node->left;
node->left = node->right;
node->right = tmp;
}
void mirror(Node* root) {
Node* current, previous;
int state;
previous = NULL;
current = root;
state = 1; // initial state
while (true) {
switch (state) {
case 1: // try left
if (current->left != NULL) {
prev_node = current;
current = current->left;
state = 1;
} else {
state = 2;
continue;
}
break;
case 2: // try right
if (current->right != NULL) {
prev_node = current;
current = current->right;
state = 1;
} else {
state = 3;
continue;
}
break;
case 3: // mirror current node
swap_branches(current);
state = 4;
break;
case 4: // try parent
if (current->parent != NULL) {
previous = current;
current = current->parent;
if (previous == current->left) {
state = 2;
} else {
stats = 3;
}
} else {
return; // done
}
default:
break;
}
}
}
PS my c++ skills is far from perfect but I hope you get the idea
This solution assumes you have a parent pointer. Also Node* current_node, prev_node; is never used. And the state is stuck at 4 after only swapping once. Solution does not work.
A simple non recursive version:
private static void mirrorBinaryTree(Node root) {
Queue<Node> queue = new LinkedList<>();
queue.add(root);
//we will get every node and swap its left and right
while(!queue.isEmpty()) {
Node current = queue.remove();
Node left = null;
Node right = null;
if(current.left != null){
left = current.left;
queue.add(left);
}
if(current.right != null){
right = current.right;
queue.add(right);
}
//swap left and right
Node temp = right;
current.right = left;
current.left = temp;
}
}
public static void main(String[] args) throws IOException {
nodes rootNode = new nodes(4);
rootNode.leftNode = new nodes(2);
rootNode.rightNode = new nodes(5);
rootNode.leftNode.leftNode = new nodes(1);
rootNode.leftNode.rightNode = new nodes(3);
rootNode.rightNode.leftNode = new nodes(6);
rootNode.rightNode.rightNode = new nodes(7);
printTree(rootNode);
System.out.println();
nodes newRoot = mirrorTree(rootNode);
printTree(newRoot);
}
public static void printTree(nodes Node)
{
if(Node == null)
return;
printTree(Node.leftNode);
System.out.print(Node.data+" ");
printTree(Node.rightNode);
}
private static nodes mirrorTree(nodes rootNode) {
nodes Root = rootNode;
if(Root == null)
{
return Root;
}
mirrorTree(Root.leftNode);
mirrorTree(Root.rightNode);
nodes temp = Root.leftNode;
Root.leftNode = Root.rightNode;
Root.rightNode = temp;
return Root;
}
}
class nodes
{
int data;
nodes leftNode;
nodes rightNode;
nodes rootNode;
nodes(int data)
{
this.data = data;
}
- Vir Pratap Uttam May 04, 2015