Groupon Interview Question
Software Engineer in TestsCountry: 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