Amazon Interview Question
SDE1sTeam: Kindle
Country: India
Interview Type: Written Test
Read tree level by level.
Maintain 2 ArrayLists of integers, one to store the current parent nodes and one to store current children nodes.
Also maintain a boolean leftToRight that will switch from true to false on every iteration.
public void printZigZag(Node root) {
boolean leftToRight = true;
ArrayList<Integer> parents = new ArrayList<Integer>();
ArrayList<Integer> children = new ArrayList<Integer>();
parents.add(root);
print(parents, leftToRight); // Helper method to print a list in a given direction
while (parents.length > 0) {
if (leftToRight) { // Next row will be left to right
for (int i = 0; i < parents.length; i++) {
if (parents[i].left != null) {
children.add(parents[i].left);
}
if (parents[i].right != null) {
children.add(parents[i].right);
}
}
} else { // Next row will be right to left
for (int i = parents.length - 1; i >= 0; i--) {
if (parents[i].right != null) {
children.add(parents[i].right);
}
if (parents[i].left != null) {
children.add(parents[i].left);
}
}
}
print(parents, leftToRight);
parents = children;
leftToRight = !leftToRight;
}
}
public void zigZagTraverse(Node n){
LinkedList<Node> l = new LinkedList<>();
l.add(n);
zigZagTraverseRecurse(l,true);
}
public void zigZagTraverseRecurse(LinkedList<Node> l, boolean reverse){
LinkedList<Node> newL = new LinkedList<>();
while(l.size()>0){
Node n = reverse?l.pollLast():l.pollFirst();
System.out.println(n.dat);
if (n.left != null){
newL.addLast(n.left);
}
if (n.right != null){
newL.addLast(n.right);
}
}
System.out.println("");
if (newL.size()>0) {
zigZagTraverseRecurse(newL,!reverse);
}
}
- Vir Pratap Uttam May 10, 2015