## Amazon Interview Question

Production Engineers**Team:**kindle

**Country:**India

**Interview Type:**In-Person

{{

static List<node1> listofnodes=new ArrayList<node1>();

void verticalSum(node1 p)

{

int verticalsum=0;

List<Integer> vertcalnodes =new ArrayList<Integer>();

if(listofnodes.contains(p)==false)

{

if(p!=null)

{

vertcalnodes.add(p.val);

if(p.left!=null)

{

node1 q=p.left;

boolean b=false;

while(q.right!=null)

{

q=q.right;

b=true;

}

if(b==true)

{

verticalsum+=q.val;

listofnodes.add(q);

vertcalnodes.add(q.val);

}

}

if(p.right!=null)

{

node1 q=p.right;

boolean b=false;

while(q.left!=null)

{

q=q.left;

b=true;

}

if(b==true)

{

verticalsum+=q.val;

listofnodes.add(q);

vertcalnodes.add(q.val);

}

}

verticalsum+=p.val;

System.out.println("Vertcal val for node :"+vertcalnodes+"is ="+verticalsum);

verticalSum(p.left);

verticalSum(p.right);

}

}

}

}}

i am just checking left or right child is there for the perticuler node or not.if its present then i am traversing to its at most oposite direction.

if(p.left!=null)

{//checking left child present or not

node1 q=p.left;

boolean b=false;

while(q.right!=null)

{//traversing to at most right successor

q=q.right;

b=true;

}

if(b==true)

{

/*if the right successor is present then i am just taking the sum and adding those node in the arraylist (listofnodes) to keep the previous recordand we are

adding vertical nodes(vertcalnodes.add(q.val);) only for showing those nodes for which we are going to calculate the vertical sum for that perticuler recursive call*/

verticalsum+=q.val;

listofnodes.add(q);

vertcalnodes.add(q.val);

}

}

/*and here listofnodes is used to see that the paerticuler node has been travased previously or not*/

```
public class BinaryTree {
private static class Node {
int key;
Node left;
Node right;
}
private Node root;
// Find left most dist
private int leftHorizontalDist() {
int dist = 0;
Node node = root;
while (node != null) {
++dist;
node = node.left;
}
return dist;
}
// Find right most dist
private int rightHorizontalDist() {
int dist = 0;
Node node = root;
while (node != null) {
++dist;
node = node.right;
}
return dist;
}
// index - horizontal dist of the node relative to the left most node.
private void fillVerticalDist(Node node, int index, int[] dist) {
if (node == null) {
return;
}
dist[index] += node.key;
fillVerticalDist(node.left, index - 1, dist);
fillVerticalDist(node.right, index + 1, dist);
}
public int[] getVerticalDist() {
if (root == null) {
return null;
}
int leftDist = leftHorizontalDist();
int rightDist = rightHorizontalDist();
int dist[] = new int[leftDist + rightDist + 1];
fillVerticalDist(root, leftDist, dist);
return dist;
}
}
```

It should work

```
void print_vert_sum(treeptr head) {
if(!head)
return;
if(head->leftchild)
printf("%d ", leftmost(head->leftchild));
move_inorder(head);
if(head->rightchild)
printf("%d ", rightmost(head));
}
void move_inorder(treeptr ptr) {
if(ptr) {
move_inorder(ptr->leftchild);
if(ptr->leftchild || ptr->rightchild)
vertical_sum(ptr);
move_inorder(ptr->rightchild);
}
}
int leftmost(treeptr ptr) {
while(ptr->leftchild)
ptr = ptr->leftchild;
return ptr->data;
}
int rightmost(treeptr ptr) {
while(ptr->rightchild)
ptr = ptr->rightchild;
return ptr->data;
}
void vertical_sum(treeptr ptr) {
int left = left_rightmost(ptr->leftchild);
int right = right_leftmost(ptr->rightchild);
printf("%d ", ptr->data + left + right);
}
int left_rightmost(treeptr ptr) {
if(!(ptr && ptr->rightchild))
return 0;
while(ptr->rightchild)
ptr = ptr->rightchild;
return ptr->data;
}
int right_leftmost(treeptr ptr) {
if(!(ptr && ptr->leftchild))
return 0;
while(ptr->leftchild)
ptr = ptr->leftchild;
return ptr->data;
}
```

- Andres December 18, 2011