Amazon Interview Question Software Engineer / Developers
Country: United States
Interview Type: Phone Interview
that';s the way to calculate. recursively evaluate the left and right subtree and carryout the operation
You missed a base case. What if you recurse on an operand node with only 1 child, your code will break.
you need to have the base case:
{{
if(node==null) return 0;
}}
to deal with that case. It is possible to have unary operators such as - with only 1 child.
"Any order is fine" ... I don't know what to say to that. The value depends on the order, ya' know? You might as well just say "any value is fine", then...
Hmm root node is %, root-left node is 1 and root-right is "+".
root-right-left node is '5' and right is '8'.
so he wanted 1%(5+8)....i could not get this so in the end he said any order is fine..hope this clears
You need to do a pre order traversal and push the elements you get out of the traversal into a stack. So you will get a prefix notion like % 1 + 5 8. Now pop the elements out of stack one by one till you get an operand. Store the numbers you popped out in a temp list. When ever you get an operand, apply the operation on the previously popped out numbers and push the value back into the stack. Do this till you pop out every element from the stack.
Hope this helps
Do a post order recursive traversal and return the value calculated for the subtree under each node
if the expression is "a+b*c+d".its preorder is "++a*bcd"
now iterate through the preorder expression in reverse order.
i.e in order dcb*a++.
while iterating if you get operand push on to stack.if it is an operator pop the stack take it as first elment and pop the stack once again to get second element.apply the operator on first element secdond element.then push it on to the stack.
in above example
push(d)
push(c)
push(b)
temp=pop()*pop()
push(temp)
push(a)
temp=pop(a)+pop(b*c)
push(temp)
pop()+pop()
this is the final result
- jobseeker April 18, 2012int evaluateTree( Node *node) { if (node->left==node-right==NULL) return node->data; int a= evaluateTree(node->left); int b= evaluateTree(node->right); return soOperation(node->data, a, b); }