Amazon Interview Question SDE-2s
Team: Hydrabad
Country: India
Interview Type: Written Test
public int pathSum (TreeNode node){
List<Integer> list = new ArrayList<Integer> ();
doPathSum (node,0,list);
int sum = 0 ;
for (int i= 0 ; i < list.size() ;++i) {
sum += list.get(i);
}
return sum;
}
public void doPathSum(TreeNode node, int sum, List<Integer> list){
if (node == null ) {
return ;
}
if (node.left == null && node.right == null) {
list.add(sum * 10 + node.val);
} else{
sum = sum * 10 + node.val;
doPathSum (node.left, sum , list);
doPathSum (node.right, sum , list);
}
}
public static class TreeNode {
int val;
TreeNode left;
TreeNode right;
TreeNode(int x) { val = x; }
}
//Java solution using recursion
private static void computeSum(Node node, long parentNodeValue,long[] runnningTotal) {
if(node == null) return ;
long currentNodeValue = parentNodeValue*10 + node.value;
if(node.left == null && node.right==null) {
runnningTotal[0] += currentNodeValue;
return ;
}
computeSum(node.left,currentNodeValue,runnningTotal);
computeSum(node.right,currentNodeValue,runnningTotal);
}
public static void main(String[] args) {
// TODO Auto-generated method stub
Node root = new Node();
root.value = 6;
Node left = new Node();
left.value = 3;
Node right = new Node();
right.value = 5;
root.left = left;
root.right = right;
left.left = new Node();
left.left.value = 2;
left.right = new Node();
left.right.value = 5;
left.right.left = new Node();
left.right.left.value = 7;
left.right.right = new Node();
left.right.right.value = 4;
right.right = new Node();
right.right.value = 4;
long [] runningTotal = new long[1];
computeSum(root,0,runningTotal);
System.out.println(runningTotal[0]);
}
static class Node {
public Node left;
public Node right;
public int value;
}
Here are two python solutions, recursive and iterative. It is basically depth first traversal with keeping path to current node, we must be careful no to account for non leaf nodes.
class Node(object):
def __init__(self, value, left=None, right=None):
self.value = value
self.right = right
self.left = left
t = Node(6,
Node(3,
Node(2),
Node(5,
Node(7),
Node(4))),
Node(5, None, Node(4)))
def path_sum(n, path=""):
"""Calculate sum of paths to leafs.
>>> path_sum(t)
13997
"""
if n is None:
return 0
this_path = path + str(n.value)
if n.left is None and n.right is None:
return int(this_path)
return (path_sum(n.left, this_path) +
path_sum(n.right, this_path))
def path_sum_iter(n):
"""Iterrative approach of finding sum of paths
>>> path_sum_iter(t)
13997
"""
s, q = 0, [(n, "")]
while q:
n, p = q.pop()
if n is None:
continue
np = p + str(n.value)
if n.left is None and n.right is None:
s += int(np)
else:
q.append((n.left, np))
q.append((n.right, np))
return s
package Practice;
public class CalculatePathSums {
public static void main(String s[]) {
Node root = new Node(6);
Node l11 = new Node(3);
Node l12 = new Node(5);
root.left = l11;
root.right = l12;
Node l21 = new Node(2);
Node l22 = new Node(5);
Node l23 = new Node(4);
l11.left = l21;
l11.right = l22;
l12.right = l23;
Node l31 = new Node(7);
Node l32 = new Node(4);
l22.left = l31;
l22.right = l32;
int sum = findSum(root, 0);
System.out.println(sum);
}
static int findSum(Node root, int sum) {
if(root.right == null && root.left == null)
sum = sum + root.data;
if(root.right != null) {
root.right.data = root.data*10 + root.right.data;
sum = findSum(root.right, sum);
}
if(root.left != null) {
root.left.data = root.data*10 + root.left.data;
sum = findSum(root.left, sum);
}
return sum;
}
}
class Node {
int data;
Node right;
Node left;
Node(int data) {
this.data = data;
}
}
package Tree;
public class PathSumToLeaves {
public static void main(String[] args) {
Node n = new Node();
n = n.insertData(1);
n.left = n.insertData(2);
n.right = n.insertData(3);
n.left.left = n.insertData(4);
n.left.right = n.insertData(5);
n.right.left = n.insertData(6);
n.right.right = n.insertData(7);
n.left.left.left = n.insertData(8);
n.left.left.right = n.insertData(9);
sumOfPathNodes(n, 0);
}
static void sumOfPathNodes(Node n ,int prevSum) {
if(n==null)
return;
if(n.left==null && n.right==null)
{
prevSum = prevSum*10 + n.data;
System.out.println(prevSum);
return;
}
else
prevSum = prevSum*10 + n.data;
sumOfPathNodes(n.left, prevSum);
sumOfPathNodes(n.right, prevSum);
}
}
I think that a recursive approach here may be simplest (alternately, two stacks could be used that store the running value (not the sum) and the position in the tree so-as-to not be recursive). However, in java, the atom structures don't easily lend themselves to changing values so use a 1 valued array or other object to store the sum. Complexity O(n) and Memory O(log n) (for balanced tree) or O(n) (if the tree is unbalanced) since it's recursive.
class SumTreeNode{
private int value,
private SumTreeNode left, right;
public static int pathSums(SumTreeNode root){
//will use this to store the result
int[] result = new int[1];
if(root != null){
pathSumsRecur(result, root, 0);
}
return result[0];
}
public static void pathSumsRecur(int[] result, SumTreeNode node, int pathSum){
pathSum *= 10;
pathSum += node.value;
boolean isLeaf = true;
if(node.left != null){
isLeaf = false;
pathSumsRecur(result, node.left, pathSum);
}
if(node.right != null){
isLeaf = false;
pathSumsRecur(result, node.right, pathSum);
}
if(isLeaf){
result[0] += pathSum;
}
}
}
/**
*
*/
package treeRelated;
/**
* @author sdinodiya
*
*/
public class pathToLeavesSum {
public static int totalSum = 0;
public static void main(String args[]) {
Node root = new Node(1);
Node left1 = new Node(2);
Node right1 = new Node(3);
//assign the value to the left and right node
root.left = left1;
root.right = right1;
Node left2 = new Node(4);
Node right2 = new Node(5);
//assign the values to the left node of the root child
root.left.left = left2;
root.left.right = right2;
Node left3 = new Node(6);
Node right3 = new Node(7);
//assign the values to the right node of the root child
root.right.left = left3;
root.right.right = right3;
System.out.println("sum is " + pathToSum(root , root.data));
}
private static int pathToSum(Node root, int sum) {
if(root.left == null && root.right == null){
System.out.println("Brach Sum:"+sum);
totalSum += sum;
}
if(root.left != null){
pathToSum(root.left, (sum*10) + root.left.data);
}
if(root.right != null){
pathToSum(root.right, (sum*10) + root.right.data);
}
return totalSum ;
}
}
public class Node {
int data;
Node left ;
Node right ;
Node (int data){
this.data = data ;
}
}
- This doesn't need extra memory allocations.
// In C++
void pathSum(node* n, int sum, int& totalSum)
{
if (n == NULL) return; // check for error condition
sum = sum*10 + n->value;
if (n->left == NULL && n->right == NULL)
{
totalSum += sum;
}
if (n->left != NULL)
{
pathSum(n->left, sum, totalSum);
}
if (n->right != NULL)
{
pathSum(n->right, sum, totalSum);
}
}
...
int result = 0;
pathSum(n, 0, result);
# -*- coding: utf-8 -*-
__author__ = 'ouyanghui'
class Node:
def __init__(self):
self.value = None
self.children = []
class TreePathSum:
def calculate(self, prefix_number, root_node):
n = len(str(root_node.value))
current_value = 10**n * prefix_number + root_node.value
if root_node.children:
return sum([self.calculate(current_value, child) for child in root_node.children])
else:
return current_value
I am re-using the algorithm from Solution 4.9 of Cracking the Coding Interview 5th Edition:
import java.util.*;
public class TreeSum
{
public static int findSum(TreeNode node)
{
final int depth = depth(node);
final int[] path = new int[depth];
final LinkedList<Integer> collectedSums = new LinkedList<Integer>();
findSum(node, path, collectedSums, 0);
int total = 0;
for (Integer pathSum: collectedSums) total+=pathSum;
return total;
}
private static void findSum(TreeNode node, int[] path, LinkedList<Integer> collectedSums,
int level)
{
if (node == null)
{
return;
}
else
{
path[level] = node.data;
if (node.left == null && node.right == null)
{
int sum = 0;
for (int i = level; i >= 0; --i)
sum += path[i] * Math.pow(10, (level-i));
collectedSums.add(sum);
}
else
{
findSum(node.left, path, collectedSums, level+1);
findSum(node.right, path, collectedSums, level+1);
path[level] = 0;
}
}
}
private static int depth(TreeNode n)
{
if (n == null) return 0;
return 1 + Math.max(depth(n.left), depth(n.right));
}
private static class TreeNode
{
TreeNode left, right;
int data;
TreeNode(int data) { this.data = data; }
}
public static void main(String[] args)
{
TreeNode root = new TreeNode(6);
root.left = new TreeNode(3);
root.right = new TreeNode(5);
root.left.left = new TreeNode(2);
root.left.right = new TreeNode(5);
root.right.right = new TreeNode(4);
root.left.right.left = new TreeNode(7);
root.left.right.right = new TreeNode(4);
final int answer = 13997;
final int totalSum = findSum(root);
assert answer == totalSum;
System.out.println(totalSum);
}
}
class Node {
int value;
Node leftNode = null;
Node rightNode = null;
public Node(int value) {
this.value = value;
}
public void addNode(Node node) {
if (value < node.value) {
if (leftNode == null) {
leftNode = node;
} else {
leftNode.addNode(node);
}
} else {
if (rightNode == null) {
rightNode = node;
} else {
rightNode.addNode(node);
}
}
}
public int calcSum() {
if (leftNode == null && rightNode == null) {
return value;
}
int retValue = 0;
if (leftNode != null) {
retValue += leftNode.calcSum(value);
}
if (rightNode != null) {
retValue += rightNode.calcSum(value);
}
return retValue;
}
private int calcSum(int parentValue) {
int sum = parentValue * 10 + value;
int retValue = 0;
if (leftNode == null && rightNode == null) {
return sum;
}
if (leftNode != null) {
retValue += leftNode.calcSum(sum);
}
if (rightNode != null) {
retValue += rightNode.calcSum(sum);
}
return retValue;
}
}
public class Main {
public static void main(String[] args) {
BinaryTree T = new BinaryTree(6);
T.specialInsert();
int answer = new AddLinkedListContnents().addLinkedLists(T.rootToLeaf());
System.out.println("answer="+answer);
}
}
import java.util.ArrayList;
public class BinaryTree {
BinaryTree left, right;
int data;
public BinaryTree(int data) {
this.data=data;
this.left=null;
this.right=null;
}
public void specialInsert() {
/* 6
/ \
3 5
/ \ \
2 5 4
/ \
7 4 */
BinaryTree T = this;
T.left=new BinaryTree(3);
T.left.left=new BinaryTree(2);
T.left.right=new BinaryTree(5);
T.left.right.left=new BinaryTree(7);
T.left.right.right=new BinaryTree(4);
T.right=new BinaryTree(5);
T.right.right=new BinaryTree(4);
}
private ArrayList<LinkedList> ArrList;
public ArrayList<LinkedList> rootToLeaf() {
ArrList=new ArrayList<LinkedList>();
rootToLead(this, new ArrayList<Integer>());
for(LinkedList L:ArrList) {
L.printList();
}
return ArrList;
}
private void rootToLead(BinaryTree T, ArrayList<Integer> path) {
if(T!=null) {
path.add(T.data);
if(T.left==null && T.right==null) {
ArrList.add(new LinkedList(path));
} else {
rootToLead(T.left, new ArrayList<>(path));
rootToLead(T.right, new ArrayList<>(path));
}
}
}
}
import java.util.ArrayList;
import java.util.Collections;
public class LinkedList {
LinkedList next;
int data;
private int size;
public LinkedList(int data) {
this.data=data;
this.next=null;
this.size++;
}
public LinkedList(ArrayList<Integer> values) {
Collections.reverse(values);
//Inserts Values in reverse
this.data=values.get(0);
this.next=null;
this.size++;
insert(values);
}
private void insert(ArrayList<Integer> values) {
int size = values.size();
if(size>0) {
LinkedList L = this;
for(int i=1; i<size; i++) {
L.next=new LinkedList(values.get(i));
L=L.next;
this.size++;
}
}
}
public void insert(int data) {
LinkedList L = this;
while(L!=null)
L=L.next;
L.next=new LinkedList(data);
this.size++;
}
public void printList() {
LinkedList L = this;
StringBuffer sb = new StringBuffer();
while(L!=null) {
sb.append(L.data).append(", ");
L=L.next;
}
System.out.println(sb.toString());
}
public int getSize() {
return size;
}
/*public void setSize(int size) {
this.size = size;
}*/
}
import java.util.ArrayList;
public class AddLinkedListContnents {
public int addLinkedLists(ArrayList<LinkedList> ALs) {
int LargestArraySize=FindLargestArraySize(ALs);
int carry = 0;
StringBuffer sb = new StringBuffer();
for(int i=0; i<LargestArraySize; i++) {
int current_sum = carry;
int size = ALs.size();
for(int j=0; j<size; j++) {
if(ALs.get(j)!=null) {
current_sum=current_sum+ALs.get(j).data;
ALs.set(j, ALs.get(j).next);
}
}
carry=current_sum/10;
current_sum=current_sum%10;
sb.append(current_sum);
current_sum=0;
}
sb.append(carry);
return Integer.parseInt(sb.reverse().toString());
}
private int FindLargestArraySize(ArrayList<LinkedList> ALs) {
int size=0;
for(LinkedList L:ALs) {
if(size<L.getSize())
size=L.getSize();
}
return size;
}
}
- Vir Pratap Uttam May 10, 2015private static void printPaths(BinaryTreeNode root, int[] path, int pathLen) { if(root==null) return; path[pathLen]=root.getData(); pathLen++; if(root.getLeft()==null && root.getRight()==null) { printArray(path,pathLen); } else { printPaths(root.getLeft(),path,pathLen); printPaths(root.getRight(),path,pathLen); } } private static void printArray(int[] path, int pathLen) { int sum=0; for(int i=0;i<pathLen;i++) { sum+=path[i]; System.out.print(path[i]+ "->"); } totalsum+=sum; System.out.println(" "+sum); }