Amazon Interview Question
Software Engineer / DevelopersTeam: AWSP
Country: United States
Interview Type: Phone Interview
I have also end up with same solution using Scala
case class Tree[+T](val value:T, val left:Option[Tree[T]], val right:Option[Tree[T]])
def zeroIfNone(t:Option[Tree[Int]]):Int = t match {
case None=>0
case Some(t)=>t.value
}
def sum(t:Option[Tree[Int]]):Option[Tree[Int]] = t match {
case None => None
case Some(t) => {
val newValue = zeroIfNone(t.left) + zeroIfNone(t.right)
Some(Tree(newValue, sum(t.left), sum(t.right)))
}
}
I have also end up with same solution using Scala
case class Tree[+T](val value:T, val left:Option[Tree[T]], val right:Option[Tree[T]])
def zeroIfNone(t:Option[Tree[Int]]):Int = t match {
case None=>0
case Some(t)=>t.value
}
def sum(t:Option[Tree[Int]]):Option[Tree[Int]] = t match {
case None => None
case Some(t) => {
val newValue = zeroIfNone(t.left) + zeroIfNone(t.right)
Some(Tree(newValue, sum(t.left), sum(t.right)))
}
}
Wrong code. You will get seg fault.
Here is a working code:
Node createReqTree(Node root){
if(root == NULL)
return NULL;
Node l=createReqTree(root->left);
Node r=createReqTree(root->right);
int total= ((l==NULL)?0:l->value) + ((r==NULL)?0:r->value);
total+= ((root->left == NULL) ? 0:root->left->value) + ((root->right == NULL)?0:root->right->value);
Node n = createNode(total);
n->left=l;
n->right=r;
return n;
}
I am not sure, if below solution is appropriate or not? Please correct me if anything wrong.
Steps:
1. First build BST with Preorder values.
2. Then do a Postorder traversal and update root as (root + (left + right)) and mark left and right as 0.
3. follow the step 2 till end of Post order.
I am not sure, if below solution is appropriate or not? Please correct me if anything wrong.
Steps:
1. First build BST with Preorder values.
2. Then do a Postorder traversal and update root as (root + (left + right)) and mark left and right as 0.
3. follow the step 2 till end of Post order.
int sumDescendant(struct node* Node)
{
if(Node == NULL)
return 0;
int cache = Node->data;
Node->data = sumDescendant(Node->left) + sumDescendant(Node->right);
return (cache + Node->data);
}
Step1: Return 0 when a Node is NULL (this is useful in assigning 0 to leaf nodes)
Step 2: Cache Node's current data since we would need to use this cached data as well later.
Step 3: Calculate the new value of the node's data by summing up its childern values
Step 4: Return cached + node's current data to the parent
Seems like the focus should be on constructing the new tree and not on reconstructing the original tree from just the preorder traversal. It's just not possible to arrive at a unique tree with just that.
Node[1] would hold the new root for a non-null tree.
public Node[] sum(Node root) {
if(root == null) {
return null;
}
Node newRoot = new Node(0);
Node sum = new Node(0);
if(root.getLeft() != null || root.getRight() != null) {
Node[] leftSum = sum(root.getLeft());
Node[] rightSum = sum(root.getRight());
sum = add(leftSum, rightSum);
newRoot.setData(sum.getData());
if(leftSum != null) {
newRoot.setLeft(leftSum[1]);
}
if(rightSum != null) {
newRoot.setRight(rightSum[1]);
}
}
return new Node[] { root, newRoot };
}
private Node add(Node[] left, Node[] right) {
int lSum = left == null ? 0 : left[0].getData();
int rSum = right == null ? 0 : right[0].getData();
return new Node(lSum + rSum);
}
You can more form than one binary trees for a given preorder traversal. That means there could be more than one solution preorder sequences. For eg, for the given preorder traversal if you form a binary tree with all left pointers NULL, then the solution sequence is (320, 270, 240, 230, 190, 130, 0) not (270, 50, 0, 0, 130, 0, 0) as mentioned in the question . This is also is the easiest solution sequence that can be formed - cumulative sum.
Can the original poster confirm that he is not missing something?
Here in the same traversal new node is created using new left and right subtrees using post order recursive alg
Node * postOrder(Node* oldNodeCurrent)
{
int leftVal = 0, rightVal = 0;
If (oldNodeCurrent == NULL)
return NULL;
Node *leftN = postOrder(oldNodeCurrent->left);
Node *rightN = postOrder(oldNodeCurrent->right);
if(leftN != NULL)
leftVal = leftN->val;
if(rightN != NULL)
rightVal = right->val;
Node* current = new Node(leftVal + rightVal,leftN,rightN);
return current;
}
Here in the same traversal new node is created using new left and right subtrees using post order recursive alg
Node * postOrder(Node* oldNodeCurrent)
{
int leftVal = 0, rightVal = 0;
If (oldNodeCurrent == NULL)
return NULL;
Node *leftN = postOrder(oldNodeCurrent->left);
Node *rightN = postOrder(oldNodeCurrent->right);
if(leftN != NULL)
leftVal = leftN->val;
if(rightN != NULL)
rightVal = right->val;
Node* current = new Node(leftVal + rightVal,leftN,rightN);
return current;
}
simple function can do the work.. transverse through the original tree ..
node * func1(node *root) {
node* root1=new node;
root1->value=0;
root1->value=sum(root);
if (root->left!=NULL)
root1->left=finc1(root->left);
if (root->right!=NULL)
root1->right=finc1(root->right);
return(root1);
}
the above solution is O(nlogn)
below is the solution in the O(N)
node * func1(node *root) {
node* root1=new node;
root1->value=0;
if (root->left!=NULL)
root1->left=finc1(root->left);
if (root->right!=NULL)
root1->right=finc1(root->right);
if(root->left==NULL && root->right==NULL)
root1->value=0;
else if(root->left!=NULL && root->right==NULL)
root1->value=root1->left+root->left;
else if(root->left==NULL && root->right!=NULL)
root1->value=root1->right+root->right;
else
root1->value=root1->right+root->right+root1->left+root->left;
return(root1);
}
This is what I came up with the help of Interviewer
private Node SumTree(Node root)
{
if (root == null) return null;
if (root.left == null && root.right == null)
return new Node(0);
Node left = SumTree(root.left);
Node right = SumTree(root.right);
int sum = left.key + right.key + root.left.key + root.right.key;
Node newroot = new Node(sum);
newroot.left = left;
newroot.right = right;
return newroot;
}
My solution
#include <stdlib.h>
int create_sum_tree(TreeNode* node, TreeNode** sumTreeNode) {
if (node == NULL)
return 0;
*sumTreeNode = calloc(1, sizeof(TreeNode));
(*sumTreeNode)->data = create_sum_tree(node->left, &((*sumTreeNode)->left)) +
create_sum_tree(node->right, &((*sumTreeNode)->right));
return node->data + (*sumTreeNode)->data;
}
My solution
#include <stdlib.h>
int create_sum_tree(TreeNode* node, TreeNode** sumTreeNode) {
if (node == NULL)
return 0;
*sumTreeNode = calloc(1, sizeof(TreeNode));
(*sumTreeNode)->data = create_sum_tree(node->left, &((*sumTreeNode)->left)) +
create_sum_tree(node->right, &((*sumTreeNode)->right));
return node->data + (*sumTreeNode)->data;
}
Assuming a trivial three element list-based representation of a BST tree, here is a complete example.
scheme <<END
(define (sumtree tree)
(define (process tree)
(if (list? tree)
(let ((left (process (cadr tree))) (right (process (caddr tree))))
(let ((sum (+ (car left) (car right))))
(list
(+ (car tree) sum)
(list sum (cadr left) (cadr right)))))
(list tree 0)))
(cadr (process tree)))
(sumtree '(50 (30 40 10) (60 55 75)))
END
Assuming a trivial three element list-based representation of a BST tree, here is a complete example.
scheme <<END
(define (sumtree tree)
(define (process tree)
(if (list? tree)
(let ((left (process (cadr tree))) (right (process (caddr tree))))
(let ((sum (+ (car left) (car right))))
(list
(+ (car tree) sum)
(list sum (cadr left) (cadr right)))))
(list tree 0)))
(cadr (process tree)))
(sumtree '(50 (30 40 10) (60 55 75)))
END
node* trees_programs::newtree(node* n)
{ node*n1=0;
node*n2=0;
if(n==0)
return NULL;
n1=newtree(n->left);
n2=newtree(n->rite);
node* nd=new node(0);
if(n==root)
{
root2=nd; // root of new tree
}
nd->left=n1;
nd->rite=n2;
nd->data=0;
if(n->left==0&&n->rite==0)
{
nd->data=0;
nd->left=0;
nd->rite=0;
}
if(n->left!=0)
nd->data+=n->left->data;
if(n->rite!=0)
nd->data+=n->rite->data;
if(n1!=0)
nd->data+=n1->data;
if(n2!=0)
nd->data+=n2->data;
return nd;
}
This is what I came up with the help of Interviewer
- sk February 23, 2012