## Amazon Interview Question Software Engineer / Developers

• 0

Given the Pre-order of the BST .check if each non-leaf node has only one child.Linear Time is expected.

Country: India
Interview Type: Phone Interview

Comment hidden because of low score. Click to expand.
7
of 15 vote

boolean checkOneChild(int[] preorder)
{
for(int i=0; i<preorder.length-2; i++)
{
int a = preorder[i]-preorder[i+1];
int b = preorder[i]-preorder[preorder.length-1];
if(a*b<0)
return false;
if(a*b==0)
{
if(a+b<0)
return false;
}
}
}

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

+1

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

can u please explain the logic with some example ?

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

-1.

Why does the BST have to contain ints?

Silly solution.

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

Logic is Simple. Vinci is checking, if the child node and the leaf node(last node) lies on the same side (Left or Right) of the Sub Tree. Means if the a*b is <0 means
1. Child is smaller then parent(i) and Last Node is greater then parent(i)
2. Child is Greater then parent(i) and Last Node is smaller then parent(i)

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

if all the internal modes in BST have only one child then its preorder has a special property i.e. every element is min or max of all the succeeding elements.
let there be n elements in preorder.
check(int p[])
{
int min,max,i;
if(p[n-1]<p[n-2])
{
min=p[n-1];
max=p[n-2];
}
else
{
min=p[n-2];
max=p[n-1];
}
for(i=n-3;i>=0;i--)
{
if(p[i]>max)
max=p[i];
else if(p[i]<min)
min=p[i];
else
return 0;
}
return 1;
}

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

Vinci's approach is good, but the code sucks.

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

Ashish's approach seems good too. Reminds me of check if a given binary tree is a BST problem.

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

cud sum1 tell me the wat is the utility of chkin
if(a.b==0) and also y (a+b<0) is chkd??

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

There is a problem with a+b<0. Consider the below tree.

``````5
/  \
1   5``````

The preorder traversal is: 5,1,5
a=5-1=4
b=5-5=0
a*b==0 But a+b>0, the function returns TRUE. But, it should return FALSE.

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

Lol -100

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

@shondik
bt in the normal bst we dont have the duplicates how cum the example taken valid then??

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

@codinglearner, then why the condition if(a*b==0) raised here?

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

@shondik
dats wat i cudnt figure out...:(
n confused

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

According to Wiki also :
"The right subtree of a node contains only nodes with keys greater than or equal to the node's key."

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

This code doesn't work for any of these inputs:
{{
{12,8,5,2,7,10,11,9,15,14,18}

{12,8,5,2,7,10,9,15,14,18}

{12,8,5,2,7,10,9}
}}

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

``````bool checkSingleChild(int[] preOrder, int n) {
int min, max, i;
min = max = preOrder[n-1];

for ( i = n-2; i>=0; i-- ) {
int term = preOrder[i];

if ( term > max )  max = term;
else if ( term < min )  min = term;
else return false;
}

return true;
}``````

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

``````Suppose your tree contains
5
\
5``````

In your case it will return false !!

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

It's a BST and there should not be a duplicate.

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

A small correction will do

``````if ( term >= max )
max = term;

else if ( term <= min )
min = term;

else
return false;``````

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

@hari@hbiz.in

According to wiki and any general idea :

In computer science, a binary search tree (BST), which may sometimes also be called an ordered or sorted binary tree, is a node-based binary tree data structure which has the following properties:[1]
The left subtree of a node contains only nodes with keys less than the node's key.
The right subtree of a node contains only nodes with keys greater than or equal to the node's key.
Both the left and right subtrees must also be binary search trees.

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

The logic is simple. For a node, all successors are either less our greater than that node. Implementation may differ from person to person.

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

and I wonder still other people replying to this question. I think It was asked as an appetizer question.

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

Theres also a NlogN solution for this problem.

Since its a BST and not a regular binary tree, we can reconstruct the binary tree from the pre-order traversal.

Algo::
a) First Element of the array is root.
b) Scan the array till we encounter an element greater than the root. This element marks the beginning of the right subtree.
c) Now, we have the elements of both the left and right tree. So, we recursively apply the above algorithm.

This algorithm will take NLogN time.

Once the BST is constructed, we can do a tree traversal and determine the internal nodes with one/two children in linear time

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

This comment has been deleted.

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

if the tree is

5
2 6
3
4
then the pre order is 5 2 3 4 6 , but ur algo returns true for this even though 5 has 2 children!

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

@suitsrk: !(3 < 4 && 3 < 6) => 1 and returns 0..

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

``````#include<stdio.h>
#include<limits.h>
int main()
{
int count=0,*p;
scanf("%d",&count);
int i=0;
p=(int *)malloc(sizeof(int)*count);
for(i=0;i<count;i++)
{
scanf("%d",&p[i]);
}
int max=INT_MAX,min=INT_MIN;
for(i=0;i<count;i++)
{
if(p[i]>max || p[i]<min)
break;
if(p[i+1]>p[i])
{
min=p[i];
}
else
{
max=p[i];
}
}
if(i==count)
printf("true");
else
printf("false");
}``````

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

your solution will not work for this input :

``````5
/  \
1   5``````

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

This is almost same as what @LoocalVinci's logic is.

``````int checkEachNodeOneChild (int* arr, int size) {
int i, a, b ;
for ( i = 0 ; i < size-2 ; i ++ ) {
a = arr[i] - arr[size-1] ;
b = arr[i] - arr[i+1] ;
if ( a*b < 0 )
return 0 ;
if ( a*b == 0 ) {
if ( a == 0 ) {
// This means root has all its child in right subtree
if ( b > 0 )
return 0 ;
}
}
}
return 1 ;
}``````

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

rebuilt the bst.
This is oN algorithm!

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

check the array from end. each element should be greater than max or less than min for the rest of the array.

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

Hi Guys

I normally don't comment on these questions, but I feel everyone has it wrong here. In a Pre-Order traversal where all non-leaf nodes have two children, what property can on extract? The thing to look for is that if a node value decreases, then there must be an increase somewhere. In other words, if a parent node has a left child (a decrease in value), then there must also be an increase value (a right child) in order for that parent to have two children. In short, if you count the number of times a node increases, and the number of times a node decreases, then in a tree with each non-leaf node that has two children, it should balance out perfectly.

Here is the algorithm

``````bool checkOneChild(vector<int> preOrderList) {
if (preOrderList.size() == 1) return true; //Only root node is present, so return true;
int increaseDecreaseCounter = 0; //long name, I know
int prev = preOrderList[0];

for (int i=1; i < preOrderList.size(); i++) {
if (preOrderList[i] >= prev)
increaseDecreaseCounter++;
else
increaseDecreaseCounter--;

prev = preOrderList[i];
}

return (increaseDecreaseCounter == 0);
}``````

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.