Amazon Interview Question Developer Program Engineers
Country: India
Interview Type: Written Test
Used this as the example Tree:
20
/ \
8 22
/ \ / \
5 3 4 25
/ \
10 14
The map idea is a great one. In java, should use the LinkedHashMap to ensure O(n) retrieval of the columns:
static class TreeNode{
TreeNode left, right;
int val;
}
public static void verticalTraverse(TreeNode node){
if(node == null){
return;
}
LinkedHashMap<Integer, ArrayList<TreeNode>> map = new LinkedHashMap<Integer, ArrayList<TreeNode>>();
int rightCount = 0;
verticalTraverseRecur(node, map, rightCount);
StringBuilder builder =new StringBuilder();
for(ArrayList<Node> column : map.values()){
for(Node containedNode : column){
builder.append(containedNode.val);
builder.append(',');
builder.append(' ');
}
builder.append('\n');
}
}
private static void verticalTraverseRecur(TreeNode node, Map<Integer, ArrayList<TreeNode>> map, int rightCount){
//in order traversal to ensure the correct output
if(node.left != null){
verticalTraverseRecur(node.left, map, rightCount -1);
}
//add this position
ArrayList<TreeNode> column = map.get(rightCount);
if(column == null){
column = new ArrayList<TreeNode>();
map.put(rightCount, column);
}
column.add(node);
//go right
if(node.right != null){
verticalTraversRecur(node.right, map, rightCount + 1);
}
}
and sorry for that there is a problem in your solution that traverse is not in the right
order, for root column it should output like 20, 3, 4, but yours is not, and I changed your code from inorder traverse to preorder traverse. here is the code
package com.t;
import java.util.ArrayList;
import java.util.Comparator;
import java.util.HashMap;
import java.util.Map;
import java.util.TreeMap;
class TreeNode {
public int value;
public TreeNode lchild;
public TreeNode rchild;
public TreeNode(int value) {
this.value = value;
}
}
public class Traverse {
public static void main(String []args) {
TreeNode root = createTree();
verticalTraverse(root);
}
public static TreeNode createTree() {
TreeNode root = new TreeNode(20);
root.lchild = new TreeNode(8);
root.rchild = new TreeNode(22);
root.lchild.lchild = new TreeNode(5);
root.lchild.rchild = new TreeNode(3);
root.lchild.rchild.lchild = new TreeNode(10);
root.rchild.lchild = new TreeNode(4);
root.rchild.rchild = new TreeNode(25);
root.rchild.lchild.rchild = new TreeNode(14);
return root;
}
public static void verticalTraverse(TreeNode root) {
if (null == root)
return;
int pos = 0;
Map<Integer, ArrayList<TreeNode>> map = new HashMap<Integer, ArrayList<TreeNode>>();
verticalTraverseUtil(root, map, pos);
Map<Integer, ArrayList<TreeNode>> resultMap = sortMapByKey(map);
StringBuilder sb = new StringBuilder();
for (ArrayList<TreeNode> list : resultMap.values()) {
for (TreeNode node : list) {
sb.append(node.value).append(" ");
}
sb.append("\n");
}
System.out.println(sb.toString());
}
public static void verticalTraverseUtil(TreeNode root, Map<Integer, ArrayList<TreeNode>> map, int pos) {
//in order traverse to ensure the correct output
ArrayList<TreeNode> col = map.get(pos);
if (null == col) {
col = new ArrayList<TreeNode>();
map.put(pos, col);
}
col.add(root);
if (null != root.lchild) {
verticalTraverseUtil(root.lchild, map, pos - 1);
}
if (null != root.rchild) {
verticalTraverseUtil(root.rchild, map, pos + 1);
}
}
private static Map<Integer, ArrayList<TreeNode>> sortMapByKey(Map<Integer, ArrayList<TreeNode>> map) {
Map<Integer, ArrayList<TreeNode>> sortMap = new TreeMap<Integer, ArrayList<TreeNode>>(new Comparator<Integer>() {
public int compare(Integer key1, Integer key2) {
return key1.compareTo(key2);
}
});
sortMap.putAll(map);
return sortMap;
}
}
A simple Python implementation using dictionaries.
class Node:
def __init__(self,data,level, left=None, right=None):
self.data = data
self.level = level # decrement level by -1 if you go left, add +1 if you go right
self.left = left
self.right = right
""" Construct a binary tree (not a BST) recursively """
def create_tree(root, data, level, index, dic):
if root is None:
root = Node(data[index], level)
if level in dic:
dic[level].append(data[index])
else:
dic[level] = [data[index]]
if index * 2 + 1 < len(data):
root.left = create_tree(root.left, data, level-1, index*2 + 1, dic)
if index * 2 + 2 < len(data):
root.right = create_tree(root.right, data, level+1, index*2 + 2, dic)
return root
if __name__ == "__main__":
a = [1,2,3,4,5,6,7]
root = None
dic = {}
root = create_tree(root, a, 0, 0, dic)
for key, val in sorted(dic.iteritems()):
print val
Use a hasmap, which stores key and the list of values. start with root pass key 0 and when you go left pass key-1 and key+1 for right.
- deepanshu December 17, 2014