## Deshaw Inc Interview Question

Software Engineer / Developers```
node * findMaxBST(node * root, int & N)
{
if (!root) return N=0, NULL;
if (!root->left && !root->right) return N=1, root;
int n1=0;
node * rootL=findMaxBST(root->left, n1);
int n2=0;
node * rootR=findMaxBST(root->right, n2);
if (!n1 && !n2) return N=1, root;
bool left = rootL==root->left && rootL->data<root->data;
bool right = rootR==root->right && rootR->data>=root->data;
if (left && right) return N=n1+n2+1, root;\
if (left)
if (n1+1>n2) return N=n1+1, root;
else return N=n2, rootR;
if (right)
if (n2+1>n1) return N=n2+1, root;
else return N=n1, rootL;
if (n1>n2) return N=n1, rootL;
return N=n2, rootR;
}
```

The question is not clear. The statement does not say how is the input: given a root or given an adjacency matrix of a directed or undirected graph. If it given as an adjacency matrix, the problem is a little hard (at least for me) because the maximum length could be the longest path between 2 leafs.

Also, maximum path is the maximum path from the root to leafs?

In case of a rooted binary tree where a node has a left and a right children and they want to know the height of the tree from the root, the problem is simple:

```
int height(node n)
{
if(n == null) return 0; //empty tree or child of a leaf
if(n.left == null && n.right == null) return 0; // leaf
return 1 + max(height(n.left), height(n.right));
}
```

Does anyone know an algorithm when the tree is given as adjacency matrix of a directed graph?

Here you calculate only the hight of the binary tree without checking root->left->data < root->data <= root->right->data condition.

inorder is wrong...it goes wrong in the inorder successor of the root node...max length bst means max no of nodes

//one function is like isThisBst(node *root)

// this will return 1 if tree is BST else it will return 0

// following approach will count number of nodes in the max bst in a tree

int max_length_bst(node *root)

{

if(root == NULL)

return(0);

i = 0;

j = 0;

k = 0;

if(isbst(root))

i = count(root);

if(isbst(root->left))

j = count(root->left);

if(isbst(root->right)

k = count(root);

return(max(i,j,k,max_length_bst(root->left),max_length_bst(root->right)))

}

//one function is like isThisBst(node *root)

// this will return 1 if tree is BST else it will return 0

// following approach will count number of nodes in the max bst in a tree

int max_length_bst(node *root)

{

if(root == NULL)

return(0);

i = 0;

j = 0;

k = 0;

if(isbst(root))

i = count(root);

if(isbst(root->left))

j = count(root->left);

if(isbst(root->right)

k = count(root);

return(max(i,j,k,max_length_bst(root->left),max_length_bst(root->right)))

}

class node{

int info;

node left;

node right;

public int getinfo()

{

return info;

}

public int getleft(){

return left;

}

public int getright(){

return right;

}

}

class maxb{

public static void main(String[] args)

{

ArrayList<node> st=new ArrayList<node>();

st=maxbst(root,st);

for(node nn: st)

{

System.out.println(nn.getInfo());

}

}

public static ArrayList<node> maxbst(node n, ArrayList<node> s);

{

ArrayList<node> templ=new ArrayList<node>();

templ=s;

if(n.getleft()!=null)

if(n.getinfo()>n.getleft().getinfo())

{

templ.add(n);

maxbst(n.getleft(),templ);

}

else{

templ=maxbst(n.getleft(),new ArrayList<node>());

if(templ.getSize()<s.getSize())

templ=s;

}

ArrayList<node> tempr=new ArrayList<node>();

tempr=s;

if(n.getright()!=null)

if(n.getinfo()<n.getright().getinfo())

{

templ.add(n);

maxbst(n.getright(),tempr);

}

else

{

tempr=maxbst(n.getright(), new ArrayList<node>());

if(tempr.getSize()<s.getSize())

tempr=s;

}

if(templ.getSize()>tempr.getSize())

return templ;

else

return tempr;

}

}

//This should work fine if you want to find maximum length BST.

class node{

int info;

node left;

node right;

public int getinfo()

{

return info;

}

public int getleft(){

return left;

}

public int getright(){

return right;

}

}

class maxb{

public static void main(String[] args)

{

ArrayList<node> st=new ArrayList<node>();

st=maxbst(root,st);

for(node nn: st)

{

System.out.println(nn.getInfo());

}

}

public static ArrayList<node> maxbst(node n, ArrayList<node> s);

{

ArrayList<node> templ=new ArrayList<node>();

templ=s;

if(n.getleft()!=null)

if(n.getinfo()>n.getleft().getinfo())

{

templ.add(n);

maxbst(n.getleft(),templ);

}

else{

templ=maxbst(n.getleft(),new ArrayList<node>());

if(templ.getSize()<s.getSize())

templ=s;

}

ArrayList<node> tempr=new ArrayList<node>();

tempr=s;

if(n.getright()!=null)

if(n.getinfo()<n.getright().getinfo())

{

templ.add(n);

maxbst(n.getright(),tempr);

}

else

{

tempr=maxbst(n.getright(), new ArrayList<node>());

if(tempr.getSize()<s.getSize())

tempr=s;

}

if(templ.getSize()>tempr.getSize())

return templ;

else

return tempr;

}

}

```
int MIN = 0, MAX = 0, maxNodes = 0;
Tree *largestBst = NULL, *child = NULL;
int findLargestBst (Tree *p, int min, int max, int maxNodes, Tree &* largestBst, Tree &* child)
{
if (!p)
return 0;
if (min < p->info && p->info < max)
{
int leftNodes = findLargestBst (p->left, MIN, p->data, maxNodes, largestBst, child);
Tree *leftchild = (leftNodes == 0)? NULL:child;
int rightNodes = findLargestBst (p->right , p->data, MAX, maxNodes, largestBst, child);
Tree *rightchild = (rightNodes == 0)?NULL:child;
Tree *parent = new Tree (p->data);
parent->left = leftchild;
parent->right = rightchild;
child = parent;
maxNodes = leftNodes + rightNodes + 1;
if (maxNodes > totalNodes)
{
totalNodes = maxNodes;
largestBst = parent;
}
return totalNodes;
}
else
{
findLargestBst (p, MIN, MAX, maxNodes, largestBst, child);
return 0;
}
}
Had found this code on some site. Commen if there are any extreme test cases that have been left out.
```

```
The above code has slight modifications
int findLargestBst (Tree *p, int min, int max, int &maxNodes, Tree &* largestBst, Tree &* child)
{
if (!p)
return 0;
if (min < p->info && p->info < max)
{
int leftNodes = findLargestBst (p->left, MIN, p->data, maxNodes, largestBst, child);
Tree *leftchild = (leftNodes == 0)? NULL:child;
int rightNodes = findLargestBst (p->right , p->data, MAX, maxNodes, largestBst, child);
Tree *rightchild = (rightNodes == 0)?NULL:child;
Tree *parent = new Tree (p->data);
parent->left = leftchild;
parent->right = rightchild;
child = parent;
int totalNodes = leftNodes + rightNodes + 1;
if (maxNodes < totalNodes)
{
maxNodes = totalNodes;
largestBst = parent;
}
return totalNodes;
}
else
{
findLargestBst (p, MIN, MAX, maxNodes, largestBst, child);
return 0;
}
}
Had found this code on some site. Comment if there are any extreme test cases that have been left out.
```

#include <stdio.h>

#include<stdlib.h>

#include<limits.h>

struct node

{

int data;

struct node *left, *right;

};

//function to create a node

struct node * createNode(int val)

{

struct node *temp = (struct node *)malloc(sizeof(struct node));

temp->data = val;

temp->left = temp ->right = NULL;

return temp;

}

//print tree in inorder

void printInorder(struct node *head)

{

if(!head)

return;

else

{

printInorder(head->left);

printf("%d->",head->data);

printInorder(head->right);

}

}

//function to check maximum length in a binary tree

int findLength(struct node *root, int min,int max,int len)

{

int max_len = len;

int max_right, max_left;

//if root is null then return length-1.

//len-1 because node is null so parent should get original length back

if(!root)

return len-1;

//check if node satisifes bst property

//if yes then increment length by 1 and process child nodes

//left child node will be smaller than this node

//right child node will be atleast equal to this node

if((min <= root->data) && (root->data < max))

{

//printf("\nmin : %d max: %d data : %d len : %d",min,max,root->data,max_len);

max_left = findLength(root->left,min,root->data,len+1);

max_right = findLength(root->right,root->data,max,len+1);

}

else

{

//else start fresh from current node as length equal to 0

//and min max rules as stated above in comment

max_left = findLength(root->left,min,root->data,0);

max_right = findLength(root->right,root->data,max,0);

}

//finally max length is maximum of current length, left tree length and right tree length

if(max_len < max_left)

max_len = max_left;

if(max_len < max_right)

max_len = max_right;

return max_len;

}

//program execution starts from here

int main(void)

{

int min = INT_MIN;

int max = INT_MAX;

// create a binary tree

struct node *head = NULL;

head = createNode(1);

head->left = createNode(2);

head->right = createNode(3);

(head->left)->left = createNode(4);

(head->left)->right = createNode(9);

(head->left)->right->left = createNode(7);

(head->left)->right->right = createNode(19);

(head->right)->left = createNode(12);

(head->right)->right = createNode(16);

head->right->right->left = createNode(14);

//head->right = createNode(2);

head->right->right->left->left = createNode(8);

head->right->right->left->right = createNode(15);

head->right->right->left->left->left = createNode(5);

head->right->right->left->left->right = createNode(10);

// print binary tree created using inorder

printInorder(head);

//function call to check length

printf("\nmax length is : %d\n", findLength(head,min,max,0));

return 0;

}

```
#include <stdio.h>
#include<stdlib.h>
#include<limits.h>
struct node
{
int data;
struct node *left, *right;
};
//function to create a node
struct node * createNode(int val)
{
struct node *temp = (struct node *)malloc(sizeof(struct node));
temp->data = val;
temp->left = temp ->right = NULL;
return temp;
}
//print tree in inorder
void printInorder(struct node *head)
{
if(!head)
return;
else
{
printInorder(head->left);
printf("%d->",head->data);
printInorder(head->right);
}
}
//function to check maximum length in a binary tree
int findLength(struct node *root, int min,int max,int len)
{
int max_len = len;
int max_right, max_left;
//if root is null then return length-1.
//len-1 because node is null so parent should get original length back
if(!root)
return len-1;
//check if node satisifes bst property
//if yes then increment length by 1 and process child nodes
//left child node will be smaller than this node
//right child node will be atleast equal to this node
if((min <= root->data) && (root->data < max))
{
//printf("\nmin : %d max: %d data : %d len : %d",min,max,root->data,max_len);
max_left = findLength(root->left,min,root->data,len+1);
max_right = findLength(root->right,root->data,max,len+1);
}
else
{
//else start fresh from current node as length equal to 0
//and min max rules as stated above in comment
max_left = findLength(root->left,min,root->data,0);
max_right = findLength(root->right,root->data,max,0);
}
//finally max length is maximum of current length, left tree length and right tree length
if(max_len < max_left)
max_len = max_left;
if(max_len < max_right)
max_len = max_right;
return max_len;
}
//program execution starts from here
int main(void)
{
int min = INT_MIN;
int max = INT_MAX;
// create a binary tree
struct node *head = NULL;
head = createNode(1);
head->left = createNode(2);
head->right = createNode(3);
(head->left)->left = createNode(4);
(head->left)->right = createNode(9);
(head->left)->right->left = createNode(7);
(head->left)->right->right = createNode(19);
(head->right)->left = createNode(12);
(head->right)->right = createNode(16);
head->right->right->left = createNode(14);
//head->right = createNode(2);
head->right->right->left->left = createNode(8);
head->right->right->left->right = createNode(15);
head->right->right->left->left->left = createNode(5);
head->right->right->left->left->right = createNode(10);
// print binary tree created using inorder
printInorder(head);
//function call to check length
printf("\nmax length is : %d\n", findLength(head,min,max,0));
return 0;
}
```

From max length BST, does it mean maximum height BST?

- DashDash July 27, 2010