Amazon Interview Question Software Engineer / Developers
Country: India
Interview Type: Phone Interview
@Godel sry abt the bad tree diagram but I think its not very hard to understand the question without the diagram. Is it?
Forget about the example given in the question, just imagine any tree and try to print the nodes you encounter when you move from left to right. If there are more than one nodes that are available in a given vertical line then print it from top to bottom.
@ kaush: that was only part of my issue. The other part is that what you are describing isn't really vertical unless you orient your view accordingly. Otherwise, if you are just facing the tree as it is present on your screen, then the most appropriate word you would want to use would be: diagonal.
That might all seem like a silly thing to harp on but in fact, it isn't. Before you can solve a problem, you need to understand the problem. If you want people to solve it, then you need to be rigorous in your problem statement. Problem statements in mathematics are rigorous, they follow from definitions so that everything is clearly understood, there are no assumptions. You should model your problem statements after mathematical problem statements.
@ kaush:
I fully agree with Godel - pls be rigorous about your post.
Additionally, you've mentioned about moving left to right in a tree and this to me is a horizontal movement rather than a verticat one.
I am assuming that we have to print going from the left lines to the right lines, and top to bottom on a given line.
Each node is on a vertical line and can be assigned a number. The line corresponding to the root being zero. If a node has the vertical line number v, then its left child has number v-1, and right child has v+1.
So we can do a breadth first search, collecting all nodes with the same vertical line in a list.
Once we are done, we can print the lists, in sorted order of the vertical number.
Pseudo code might look something like this
void printVerticals <T> (BinTree<T> tree) {
if (tree == null) throw...
int n = tree.Count;
// vertical line numbers are -n,-n+1, -n+2, ..., 0, 1, 2, .., n+1
// and correspond to array locations 0,1,2, ..., 2n+1
List <T> verticals[2*n+1];
Queue <BinTree<T>, int> q;
q.enQ(tree, 0);
while(q.hasElements()) {
// Python like syntax? Being lazy here.
BinTree<T> curNode, int lineNumber = q.deQ();
// Add to corresponding list.
verticals[lineNumber+n].Add(curNode);
if (curNode.Left) {
q.enQ(curNode.Left, lineNumber-1);
}
if (curNode.Right) {
q.enQ(curNode.Right, lineNumber+1);
}
}
// Assuming this iteration does in the order 0,1,2,...
foreach(List <T> vertical in verticals) {
// Assuming this iteration does in the order of insertion.
foreach (T data in vertical) {
// Print.
}
}
}
sry abt the bad tree structure
Root Node: 1
Left Child of 1: 2
Right Child of 1: 3
Left Child of 2: 4
Left Child of 3: 5
Right Child of 5: 6
General algorithm:
You are going to iterate through a hashtable depending on what group the node belongs and then print it in order from top to bottom.
1. Assign 2D coordinates to nodes
1( 0,0 )
/ \
2(-1,1) 3 (1,1)
/ / \
4(-2,2) 5(0,2) 6(2,2)
2. Sort the coordinates
-2,2
-1,1
0,0
0,2
1,1
2,2
use preorder traversal of the binary tree
class Node{
int data;
Node leftChild;
Node rightChild;
}
public void preOrder(Node localRoot){
preOrder(localRoot.leftChild);
System.out.print(localRoot.data+ " ");
preOrder(localRoot.rightChild);
}
That should do it
Hi ,
What if the two nodes are at the same level .... do you want their sum to be printed .... ??
If yes, just create a Hash data structure and index using hash levels (-1,0,1) and iterate over the hash and print the sum
printVertical(Node node){
if(node==null) return;
Stack<Node> stack = new Stack<Node>();
List<Node> queue = new ArrayList<Node>();
Node temp = node;
while(temp!=null){
stack.push(temp);
temp = temp.left;
}
while(!stack.isEmpty()){
temp = stack.pop();
if(temp.right!=null){
queue.add(temp.right);
}
PRINT(temp.data);
}
while(!list.isEmpty())
printVertical(list.remove(0));
}
package trees;
public class TreeNode {
private int data;
private TreeNode left;
private TreeNode right;
public TreeNode(int d){
this.data = d;
}
public TreeNode appendRight(int d){
this.right = new TreeNode(d);
return this.right;
}
public TreeNode appendLeft(int d){
this.left = new TreeNode(d);
return this.left;
}
public int getData() {
return data;
}
public void setData(int data) {
this.data = data;
}
public TreeNode getLeft() {
return left;
}
public void setLeft(TreeNode left) {
this.left = left;
}
public TreeNode getRight() {
return right;
}
public void setRight(TreeNode right) {
this.right = right;
}
public static void print(TreeNode node){
if(node!= null){
print(node.left);
System.out.print(node.data+ " ");
print(node.right);
}
}
}
package trees;
/**
* Imagine a vertical line sweeping the tree from Left to right and we will print
* nodes at each vertical level in an ascending order of the depth of the node
* from the root.
*/
import java.util.ArrayList;
import java.util.Collections;
import java.util.HashMap;
import java.util.List;
import java.util.Map;
public class PrintTreeVertically {
public static void main(String[] args) {
TreeNode root = new TreeNode(1);
root.appendLeft(2).appendLeft(4);
root.getLeft().appendRight(5).appendLeft(8);
root.appendRight(3).appendLeft(6);
root.getRight().appendRight(7);
Map<Integer, ArrayList<TreeNode>> nodes = new HashMap<Integer, ArrayList<TreeNode>>();
organizeNodesVertically(root, 0, nodes);
List<Integer> verticalIndices = new ArrayList<Integer>(nodes.keySet());
Collections.sort(verticalIndices);
for (Integer i : verticalIndices) {
ArrayList<TreeNode> list = nodes.get(i);
for (TreeNode treeNode : list) {
System.out.print(treeNode.getData() + " ");
}
}
}
private static void organizeNodesVertically(TreeNode root,
int verticalIndex, Map<Integer, ArrayList<TreeNode>> nodes) {
if (root == null) {
return;
}
if (nodes.get(verticalIndex) == null) {
nodes.put(verticalIndex, new ArrayList<TreeNode>());
}
nodes.get(verticalIndex).add(root);
organizeNodesVertically(root.getLeft(), verticalIndex - 1, nodes);
organizeNodesVertically(root.getRight(), verticalIndex + 1, nodes);
}
}
Algorithm:
stack.push(root)
while (!stack.empty())
{ while(stack.top().->leftchild!=NULL)
Stack.push(stack.top()->leftchild());
temp=stack.pop();
print(temp)
stack.push(temp->rightchild)
}
void BST::printVertical(Node *root,int index,map<int,vector<int>>& list) {
if ( root == NULL)
return;
vector<int> l = list[index];
l.push_back(root->value);
list[index] = l;
printVertical(root->leftChild,index-1,list);
printVertical(root->rightChild,index+1,list);
}
iterate through the map and you'll get sorted list of indexes and vectors containing vertical elements.
//Here's my two cents with o(1) space with recursion!!
//printing algo. Take any root and combine its left->right and right->left value
//ofcourse excluding those values from printing again by this condition
//if it is not root node or if it's on the root left and it is left node itself, then print it.
//if it is not root node and if it's on the root right and it is right node itself, then print it.
private static void printTreeVOrder(Node node,boolean root,boolean left,boolean rootLeft){
if(node == null) return;
if(root) {
rootLeft = true;
}
if(node.left!=null) printTreeVOrder(node.left,false,true,rootLeft);
if(root || ((left && rootLeft ) || (!left && !rootLeft)))
System.out.print(node.value);
if(node.left!=null && node.left.right!=null) System.out.print(" " + node.left.right.value);
if(node.right!=null && node.right.left!=null) System.out.print(" " + node.right.left.value);
if(root || ((left && rootLeft ) || (!left && !rootLeft)))
System.out.println();
if(node.left!=null) printTreeVOrder(node.right,false,false,(root?!rootLeft:rootLeft));
}
public static void main(String[] args) {
// TODO Auto-generated method stub
Node root = add(null, 8, false);
//level 1 nodes
Node l11 = add(root,6,true);
Node l12 = add(root,10,false);
//level 2 nodes
Node l21 = add(l11,4,true);
Node l22 = add(l11,7,false);
Node l23 = add(l12,9,true);
Node l24 = add(l12,12,false);
//level 3 nodes
Node l31 = add(l21,3,true);
Node l32 = add(l21,5,false);
printTreeVOrder(root,true,false,false);
}
private static Node add(Node parentNode,int value,boolean left) {
Node returnNode = new Node();
if(parentNode != null) {
if(left) parentNode.left = returnNode;
else parentNode.right = returnNode;
}
returnNode.value = value;
return returnNode;
}
class Node
{
public $info;
public $left;
public $right;
public $hd; // horizontal distance
public function __construct($info)
{
$this->info = $info;
$this->left = null;
$this->right = null;
$this->hd = 0;
}
public function __toString()
{
return "$this->info";
}
}
$root = new Node(5);
$root->left = new Node(4);
$root->right = new Node(3);
$root->left->left = new Node(6);
$root->left->right = new Node(7);
$root->right->left = new Node(8);
$root->right->right = new Node(9);
function bfs(Node $node)
{
$queue = array($node);
$node->hd = 0;
$output = array();
while (count($queue) > 0) {
$current_node = array_shift($queue);
$output[$current_node->hd][] = $current_node->info;
if ($current_node->left != null) {
$current_node->left->hd = $current_node->hd + 1;
array_push($queue, $current_node->left);
}
if ($current_node->right != NULL) {
$current_node->right->hd = $current_node->hd - 1;
array_push($queue, $current_node->right);
}
}
return $output;
}
$result = bfs($root);
$keys = array_keys($result);
arsort($keys);
foreach ($keys as $key) {
echo implode(' ', $result[$key]), "\n";
}
I suspect a lot of these questions posted here are posted by people that suck at math. Why? Because definitions are important. I can't reconcile any sensible definition of 'vertical' between the tree you drew up and the o/p you posted. So why not define what vertical means here for your nodes. Make sure it is rigorous too. There isn't anything interesting about wasting time trying to figure out what you are trying to say. Communication is important so don't kid yourself by thinking otherwise.
- Godel October 11, 2012