Amazon Interview Question
Software Engineer / DevelopersCountry: United States
Interview Type: Phone Interview
public class Main {
public static void computeSumAtHeights(BinaryNode tree, int currentHeight, List<Integer> sums) {
if(sums.size() <= currentHeight) {
sums.add(currentHeight, new Integer(tree.getValue()));
} else {
sums.set(currentHeight, sums.get(currentHeight) + tree.getValue());
}
if(tree.getLeft() != null) {
computeSumAtHeights(tree.getLeft(), currentHeight + 1, sums);
}
if(tree.getRight() != null) {
computeSumAtHeights(tree.getRight(), currentHeight + 1, sums);
}
}
public static void main(String... args) {
BinaryNode level2Left1 = new BinaryNode(null, null,4);
BinaryNode level2Right1 = new BinaryNode(null, null,5);
BinaryNode level1Left = new BinaryNode(level2Left1, level2Right1, 2);
BinaryNode level2Left2 = new BinaryNode(null, null,1);
BinaryNode level2Right2 = new BinaryNode(null, null,2);
BinaryNode level1Right = new BinaryNode(level2Left2, level2Right2, 3);
BinaryNode root = new BinaryNode(level1Left, level1Right,1);
List<Integer> sums = new ArrayList<Integer>(0);
computeSumAtHeights(root, 0, sums);
System.out.println(sums);
}
}
You need to traverse the tree by level, so use BFS would do the job, but standard BFS would not work because it do not have clear boundary on each level, the key is using 2 queues, code is like:
std::queue<Node*> queues[2];
vector<int> sizes;
int cur_queue_index = 0;
int next_queue_index =1;
if (root) {
queues[0].push(root);
} else {
return;
}
cout << "[";
int sum = 0;
while (!queue[cur_queue_index].empty()) {
const node * const current_node = queues[cur_queue_index].front;
queues[cur_queue_index].pop();
sum += current_node->value;
if(current_node->left) {
queues[next_queue_index].push(current_node->left);
}
if(current_node->right) {
queues[next_queue_index].push(current_node->right);
}
if(queue[cur_queue_index].empty())
{
cout << sum << ",";
sum = 0;
swap(next_queue_index, cur_queue_index);
}
}
cout << "]";
Here is C++ version of solution using BFS.
Running time O(N), Space complexity O(N).
#include<iostream>
#include<list>
using namespace std;
struct node {
int value;
node *left;
node *right;
node(int v):value(v), left(0), right(0){}
};
list<int> addup(node* r)
{
list<int> result;
list<node*> queue;
int cur_level= 0;
int next_level = 0;
int total = 0;
if (!r)
return result;
queue.push_back(r);
cur_level++;
while(queue.size())
{
node *cur = queue.front();
queue.pop_front();
if (cur->left)
{
queue.push_back(cur->left);
next_level++;
}
if (cur->right)
{
queue.push_back(cur->right);
next_level++;
}
cur_level--;
total += cur->value;
if (cur_level==0)
{
result.push_back(total);
cur_level = next_level;
next_level = 0;
total = 0;
}
}
import java.util.ArrayList;
import java.util.List;
public class SUMBST {
class TreeNode{
int value;
TreeNode left;
TreeNode right;
TreeNode(int x) { value = x; }
}
public static void SumAtLevel(TreeNode tree, int level, List<Integer> sums) {
if(sums.size() <= level) {
sums.add(level, tree.value);
} else {
sums.set(level, sums.get(level) + tree.value);
}
if(tree.left != null) {
SumAtLevel(tree.left, level + 1, sums);
}
if(tree.right != null) {
SumAtLevel(tree.right, level + 1, sums);
}
}
public static void main(String[] args) {
TreeNode root = new SUMBST(). new TreeNode(5);
TreeNode left = new SUMBST(). new TreeNode(2);
TreeNode left2 = new SUMBST(). new TreeNode(1);
TreeNode right2 = new SUMBST(). new TreeNode(4);
TreeNode right = new SUMBST(). new TreeNode(7);
TreeNode left1 = new SUMBST(). new TreeNode(6);
TreeNode right1 = new SUMBST(). new TreeNode(8);
root.left = left;
//root.left.left = left2;
//root.left.right = right2;
root.right = right;
//root.right.left = left1;
//root.right.right = right1;
List<Integer> sums = new ArrayList<Integer>(0);
SumAtLevel(root, 0, sums);
System.out.println(sums);
}
}
NB: The supplied sample isn't a BST, but it isn't important to the problem. Simple tree traversal - I use a preorder but it isn't important.
O(n) time and O(n) space (O(log n) space if your tree is unbalanced by at most a constant factor).
from data_structures import Queue
class Node(object):
def __init__(self, key):
super(Node, self).__init__()
self.key = key
self.left = None
self.right = None
def __str__(self):
return str(self.key)
def sum_levels(root):
def visit(node, i):
if node:
try:
sums[i] += node.key
except IndexError:
sums.append(node.key)
i += 1
visit(node.left, i)
visit(node.right, i)
i -= 1
sums = []
visit(root, 0)
return sums
if __name__ == "__main__":
nodes = [1, 2, 3, 4, 5, 1, 2]
q = Queue()
r = Node(nodes[0])
q.enqueue(r)
for k in range(1, len(nodes), 2):
n = q.dequeue()
n.left = Node(nodes[k])
q.enqueue(n.left)
n.right = Node(nodes[k + 1])
q.enqueue(n.right)
print(sum_levels(r))
public static ArrayList<Integer> levelSumArray(BinaryTreeNode N) {
// Now do the level-order traversal with calculating sum at every level
if (N == null)
return null;
ArrayList<Integer> myList = new ArrayList<Integer>();
Queue<BinaryTreeNode> myQueue = new LinkedList<GFG.BinaryTreeNode>();
myQueue.add(N);
myQueue.add(null);
int sum = 0;
while (!myQueue.isEmpty()) {
System.out.println(myQueue.toString());
BinaryTreeNode current = myQueue.poll();
if (current != null) {
sum = sum + current.value;
if (current.left != null) {
myQueue.add(current.left);
}
if (current.right != null) {
myQueue.add(current.right);
}
}
else {
// it could be actual end or a partition
myList.add(sum);
sum = 0;
if (!myQueue.isEmpty())
myQueue.add(null);
}
}
// myList.add(sum);
return myList;
}
public static class BinaryTreeNode {
public BinaryTreeNode left;
public BinaryTreeNode right;
public int value;
public BinaryTreeNode(int v) {
value = v;
left = null;
right = null;
}
@Override
public String toString() {
// TODO Auto-generated method stub
return Integer.toString(value);
}
}
Use a queue to store a tuple of values ( treenode, level). Start with initial sum of 0 for the root. Add the tuple (rootnode, 0) to the queue initially. Loop till the queue is empty. At each iteration check if the level of the removed node matches the current level. If it matches, then add node.data to the sum. If level is not the same, add the sum till now to the results list, reset sum to the current node.data and continue.
def findLevelOrderSumBST(root):
if root == None:
return root
results = []
level = 0; levelsum = 0
q = Queue()
q.put((root, level))
while not q.empty():
node, currlevel = q.get()
leftchild = node.left
rightchild = node.right
if leftchild != None:
q.put((leftchild, currlevel + 1))
if rightchild != None:
q.put((rightchild, currlevel + 1))
if currlevel == level:
levelsum = levelsum + node.data
else:
results.append(levelsum)
levelsum = node.data
level = currlevel
results.append(levelsum)
return results
import java.util.LinkedList;
import java.util.Queue;
public class PrintATreeLevelByLevel {
public static class Node{
int data;
public Node left;
public Node right;
public Node(int data){
this.data = data;
this.left = null;
this.right = null;
}
}
public void printATreeLevelByLevel(Node n){
Queue<Node> queue = new LinkedList<Node>();
queue.add(n);
int node = 1; //because at root
int child = 0; //initialize it with 0
while(queue.size() != 0){
Node n1 = queue.remove();
node--;
System.err.print(n1.data +" ");
if(n1.left !=null){
queue.add(n1.left);
child ++;
}
if(n1.right != null){
queue.add(n1.right);
child ++;
}
if( node == 0){
System.err.println();
node = child ;
child = 0;
}
}
}
public static void main(String[]args){
PrintATreeLevelByLevel obj = new PrintATreeLevelByLevel();
Node node1 = new Node(1);
Node node2 = new Node(2);
Node node3 = new Node(3);
Node node4 = new Node(4);
Node node5 = new Node(5);
Node node6 = new Node(6);
Node node7 = new Node(7);
Node node8 = new Node(8);
node4.left = node2;
node4.right = node6;
node2.left = node1;
// node2.right = node3;
node6.left = node5;
node6.right = node7;
node1.left = node8;
obj.printATreeLevelByLevel(node4);
}
}
Implementation: cpluspluslearning-petert.blogspot.co.uk/2015/09/bst-return-sum-of-each-level-amazon.html
Test
void TestCasesOfSumOfEachLevelOfTree()
{
std::vector<int> testInput{ 1 };
TreeNode<int>* rootBFS = ConstructTreeOnSortedValueBFS(testInput);
assert(rootBFS != nullptr);
std::vector<int> result;
GetSumOfEachLevelOfTree(rootBFS, result);
assert(result.size() == 1);
assert(result[0] == 1);
DeleteTree(&rootBFS);
testInput = {1, 2};
rootBFS = ConstructTreeOnSortedValueBFS(testInput);
assert(rootBFS != nullptr);
result.clear();
GetSumOfEachLevelOfTree(rootBFS, result);
assert(result.size() == 2);
assert(result[0] == 2);
assert(result[1] == 1);
DeleteTree(&rootBFS);
testInput = { 1, 2, 3 };
rootBFS = ConstructTreeOnSortedValueBFS(testInput);
assert(rootBFS != nullptr);
result.clear();
GetSumOfEachLevelOfTree(rootBFS, result);
assert(result.size() == 2);
assert(result[0] == 2);
assert(result[1] == 4);
DeleteTree(&rootBFS);
testInput = { 1, 2, 3, 4, 5, 6, 7, 8, 9, 10 };
rootBFS = ConstructTreeOnSortedValueBFS(testInput);
assert(rootBFS != nullptr);
result.clear();
GetSumOfEachLevelOfTree(rootBFS, result);
assert(result.size() == 4);
assert(result[0] == 6); // 6
assert(result[1] == 11);// 3, 8
assert(result[2] == 21); // 1, 4, 7, 9
assert(result[3] == 17);// 2, 5, 10
DeleteTree(&rootBFS);
}
import java.util.*;
public class SumLevels {
public static class Node<T> {
Node<T> left;
Node<T> right;
T data;
public Node() {
}
public Node(T data) {
this.data = data;
}
}
public static int heightTree(Node<?> root) {
if (root == null) {
return 0;
} else {
return 1 + Math.max(heightTree(root.left), heightTree(root.right));
}
}
public static List<Integer> sumLevels(Node<Integer> root) throws IllegalArgumentException {
List<Integer> res = new ArrayList<Integer>();
Queue<Node<Integer>> q = new LinkedList<Node<Integer>>();
int height = heightTree(root);
int breadth = 1;
if (root == null) {
throw new IllegalArgumentException("root node doesn't be null");
}
q.add(root);
res.add(root.data);
for (int i = 1; i < height; i++){
int sum = 0;
for (int j = 1; j <= breadth; j++) {
Node<Integer> n = q.poll();
if (n.left != null) {
q.add(n.left);
sum += n.left.data;
}
if (n.right != null) {
q.add(n.right);
sum += n.right.data;
}
}
res.add(sum);
breadth *= 2;
}
return res;
}
public static void main(String[] args) {
Node<Integer> root = new Node<Integer>(1);
root.left = new Node<Integer>(2);
root.right = new Node<Integer>(3);
root.left.left = new Node<Integer>(4);
root.left.right = new Node<Integer>(5);
root.right.left = new Node<Integer>(1);
root.right.right = new Node<Integer>(2);
System.out.println(sumLevels(root));
}
}
If the tree is always complete, it could be represented as an array.
Given a level n, the can obtain the index of the first element of that level, thus the only thing required is sum the elements array[n:n+1]
#!/usr/bin/env python3
from math import log2
def first_element_index(level):
return 2**level - 1
def elements_in_level(tree, level):
i = first_element_index(level)
j = first_element_index(level + 1)
return tree[i:j]
def solution(tree):
number_of_levels = int(log2(len(tree)))
sum_in_levels = []
for level in range(number_of_levels + 1):
sum_in_levels.append(sum(elements_in_level(tree, level)))
return sum_in_levels
assert solution([1, 2, 3, 4, 5, 1, 2]) == [1, 5, 12]
Note that the example tree is not a BST. Is this a misspell, or should the BST property be used to reduce space complexity.
- Alex August 30, 2015