## Groupon Interview Question

Software Engineer in Tests**Country:**India

**Interview Type:**Phone Interview

x

/ \

xl xr

/ \ / \

xll xlr xrl xrr

then tree should be like...

---xll

---xl

---x-xlr-xrl

---xr

---xrr

Assign column numbers to the nodes first...

assign root as 0, then immediate left node as -1 and right node as +1..now proceed to next level...assign -1 to left tree node and assign +1 to right tree node...now...the xlr and xrl have same column number, that is 0..hence same with the root..this is how we can print x-xlr-xrl..coz they have the same column number,,,((-1)+(+1)=0)..all left tree will have -1 and -2 as their column number now...and all right tree have +1 and +2 as their column number now...try it...pls drop ur comments if you have any other logic..

Algorithm: Do a BFS and keep the nodes in an array. So, for any index of the array i, the vertical order match would be in the relation 4i+1 and 4i+2. Use recursion to print all the nodes for a given i. For ex. for i = 1, the vertical nodes are 5, 6, (4*5+1),(4*5 +1),(4*6 +1), (4*6+2)th node of the array and so on. Print those and make those nodes infinity in the array, so that they are not printed again. Then iterate through the whole array.

```
public void printVerticalTraversal() {
Map<Integer,LinkedList<TreeNode>> hashtable = new HashMap<>();
printVerticalTraversalHelper(root,0,hashtable);
printHashTable(hashtable);
}
private void printHashTable(Map<Integer, LinkedList<TreeNode>> hashtable) {
for (Integer key : hashtable.keySet()) {
LinkedList<TreeNode> list = hashtable.get(key);
System.out.println("Key = "+key);
printList(list);
}
}
private void printList(LinkedList<TreeNode> list) {
for (TreeNode node : list) {
System.out.print(node.getData());
System.out.print(" ");
}
System.out.println("\n");
}
private void printVerticalTraversalHelper(TreeNode root, int value, Map<Integer, LinkedList<TreeNode>> hashtable) {
addToHashTable(value,root,hashtable);
if(root.getLeft()!=null)
printVerticalTraversalHelper(root.getLeft(), value-1, hashtable);
if(root.getRight()!=null)
printVerticalTraversalHelper(root.getRight(), value+1, hashtable);
}
private void addToHashTable(int value, TreeNode root,
Map<Integer, LinkedList<TreeNode>> hashtable) {
LinkedList<TreeNode> result = new LinkedList<>();
if(hashtable.containsKey(value))
result = hashtable.get(value);
result.add(root);
hashtable.put(value, result);
}
```

use list as a queue (maintain a pointer to its tail)

- gen-y-s December 03, 2012put the root node in the queue

while there are nodes in the queue:

- pop a node from the queue

- print it

- push its children to the tail of the queue

basically, it's BFS