Amazon Interview Question
Software Engineer / DevelopersThis can be done in place without additional space. Assume level n's pointers are fixed. Using these pointers, we can fix the pointers for level n+1. Explicitly fix the pointers for level 0 alone. Once it is done, apply above mentioned strategy.
Solution without additional memory.
public class MainClass {
public static void main(String[] args) {
TreeItem root = init();
linkLevel(root, true);
printTree(root);
}
private static void linkLevel(TreeItem startNode, boolean direction) {
TreeItem currentNode = startNode;
TreeItem lastSibling = null;
do {
if (direction) {
if (currentNode.left != null) {
currentNode.left.sibling = lastSibling;
if (currentNode.right != null) {
currentNode.right.sibling = currentNode.left;
lastSibling = currentNode.right;
} else {
lastSibling = currentNode.left;
}
} else if (currentNode.right != null) {
currentNode.right.sibling = lastSibling;
lastSibling = currentNode.right;
}
} else {
if (currentNode.right != null) {
currentNode.right.sibling = lastSibling;
if (currentNode.left != null) {
currentNode.left.sibling = currentNode.right;
lastSibling = currentNode.left;
} else {
lastSibling = currentNode.right;
}
} else if (currentNode.left != null) {
currentNode.left.sibling = lastSibling;
lastSibling = currentNode.left;
}
}
if (currentNode.sibling == null) {
currentNode.sibling = lastSibling;
break;
} else {
currentNode = currentNode.sibling;
}
} while (true);
if (lastSibling != null) linkLevel(lastSibling, !direction);
}
private static void printTree(TreeItem item) {
while (item != null) {
System.out.print(item.value);
System.out.print(" ");
item = item.sibling;
}
}
private static TreeItem init() {
TreeItem A = new TreeItem("A");
TreeItem B = new TreeItem("B");
TreeItem C = new TreeItem("C");
TreeItem D = new TreeItem("D");
TreeItem E = new TreeItem("E");
TreeItem F = new TreeItem("F");
A.left = B;
A.right = C;
B.left = D;
B.right = E;
C.right = F;
return A;
}
public static class TreeItem {
public TreeItem left;
public TreeItem right;
public TreeItem sibling;
public String value;
public TreeItem(String value) {
this.value = value;
}
@Override
public String toString() {
return value;
}
}
}
my solution, extrac data structure : 1 queue 2 stack
- Anonymous February 06, 2012