Amazon Interview Question
Software Engineer / DevelopersCountry: India
Interview Type: In-Person
Hey what was the interviewer reaction when u told him that u already knew this question?
Did he modify the prob....or what?
can you please explain what does vertical summation of a Binary tree mean?
May be you can give an example
sorry dude. it's a very common question and i don't have time to explain it in details. A google search or search in career cup for "vertical summation of binary tree" will help u.
public class BTVerticalSum {
public static void main(String[] args) {
Node root = Node.test2();
BTreePrinter.printNode(root);
findVerticalSum(root, root);
while(root.prev!=null){
root=root.prev;
}
while(root!=null){
System.out.print(root.data+" ");
root=root.next;
}
}
public static void findVerticalSum(Node p, Node n) {
if (p == null)
return;
if (p.left != null && p.prev == null) {
p.prev = p.left;
p.left.next = p;
}
findVerticalSum(p.left, n.prev);
if(p!=n){
n.data+=p.data;
}
if (p.right != null && p.next == null) {
p.next = p.right;
p.right.prev = p;
}
findVerticalSum(p.right, n.next);
}
}
- xiaochao October 20, 2011