## Amazon Interview Question

Software Engineer / Developers- 0of 0 votes
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

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)

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;

}

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

cud sum1 tell me the wat is the utility of chkin

if(a.b==0) and also y (a+b<0) is chkd??

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.

@shondik

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

According to Wiki also :

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

```
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;
}
```

A small correction will do

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

@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.

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

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

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!

```
#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");
}
```

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 ;
}
```

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);
}
```

boolean checkOneChild(int[] preorder)

- LoocalVinci July 31, 2012{

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;

}

}

}