## Amazon Interview Question Software Engineer / Developers

• 0

expression tree design.

Comment hidden because of low score. Click to expand.
1
of 1 vote

I think what the question means if - if you are given an infix/postfix expression, make an expression tree out of it.

Eg. Convert a postfix expression into an expression tree

Algorithm:

1. Intialize a stack to store binary tree nodes.
2. Read the array from left to right.
3. If you come across an operand, make a node out of it and push into the stack.
If its an operator, pop two nodes from the stack and first popped node would be the operator node's right child and the second popped node would be the operator node's left child. Push the operator node into the stack
4.The last popped node would be the head of the tree.

``````struct node *createTree(int a[])
{
Stack S;
struct node *new = NULL;
for(int i = 0; a[i]! = ‘\0’; i++)
{
if (arr[i] == ‘+’ || arr[i] == ‘-’ || arr[i] == ‘/’ || arr[i] == ‘*’)
{
new = newNode(a[i]);
new -> right = s1.pop();
new->left = s1.pop();
s1.push(new);
}
else
s1.push(newNode(a[i]);
}
}
return s1.pop();
}``````

Comment hidden because of low score. Click to expand.
0

This code has bug
ab+cd* gets converted to two subtrees a + b and c * d but these two subtrees are not connected and program would return only the subtree at the top.

Comment hidden because of low score. Click to expand.
0

@Anonymous: yes surely it has a bug because you are giving a wrong expression and it is not handling that condition. we might incorporate some exception here to be thrown if at last there are more than 1 nodes in the stack.

Comment hidden because of low score. Click to expand.
1
of 1 vote

If you are talking about how will you represent this in OO-world, then the answer is using Composition design pattern which is structural.

Comment hidden because of low score. Click to expand.
0
of 0 vote

I didn't understand the question.. could someone provide more info...

Comment hidden because of low score. Click to expand.
0

Swathi, check my response below

Comment hidden because of low score. Click to expand.
0

Swathi, check my response below

Comment hidden because of low score. Click to expand.
0
of 0 vote

Expression Tree is ( math or regular)..
Example: a+b +ab can be represented in a binary tree.

Design: A simple binary tree will do for Math Expression taking the inpifx

Name:

Writing Code? Surround your code with {{{ and }}} to preserve whitespace.

### Books

is a comprehensive book walking you through every aspect of getting a job at a top tech company, while focuses on software engineering interviews.

### Videos

CareerCup's interview videos give you a real-life look at technical interviews. In these unscripted videos, watch how other candidates handle tough questions and how the interviewer thinks about their performance.