Amazon Interview Question
Country: India
Interview Type: In-Person
Method 1 - Simple but Inefficient. Time Complexity is O(n^2)
Start from root and do an inorder traversal of the tree. For each node N, check whether the subtree rooted with N is BST or not. If BST, then return size of the subtree rooted with N. Else, recur down the left and right subtrees and return the maximum of values returned by left and right subtrees.
int largestBST(struct node *root)
{
if (isBST(root))
return size(root);
else
return max(largestBST(root->left), largestBST(root->right));
}
Method 2 - Efficient
Traverse tree in bottom up manner and pass information like size of BST if it is BST when you recurse back.
/* Returns size of the largest BST subtree in a Binary Tree
(efficient version). */
int largestBST(struct node* node)
{
// Set the initial values for calling largestBSTUtil()
int min = INT_MAX; // For minimum value in right subtree
int max = INT_MIN; // For maximum value in left subtree
int max_size = 0; // For size of the largest BST
bool is_bst = 0;
largestBSTUtil(node, &min, &max, &max_size, &is_bst);
return max_size;
}
/* largestBSTUtil() updates *max_size_ref for the size of the largest BST
subtree. Also, if the tree rooted with node is non-empty and a BST,
then returns size of the tree. Otherwise returns 0.*/
int largestBSTUtil(struct node* node, int *min_ref, int *max_ref,
int *max_size_ref, bool *is_bst_ref)
{
/* Base Case */
if (node == NULL)
{
*is_bst_ref = 1; // An empty tree is BST
return 0; // Size of the BST is 0
}
int min = INT_MAX;
/* A flag variable for left subtree property
i.e., max(root->left) < root->data */
bool left_flag = false;
/* A flag variable for right subtree property
i.e., min(root->right) > root->data */
bool right_flag = false;
int ls, rs; // To store sizes of left and right subtrees
/* Following tasks are done by recursive call for left subtree
a) Get the maximum value in left subtree (Stored in *max_ref)
b) Check whether Left Subtree is BST or not (Stored in *is_bst_ref)
c) Get the size of maximum size BST in left subtree (updates *max_size) */
*max_ref = INT_MIN;
ls = largestBSTUtil(node->left, min_ref, max_ref, max_size_ref, is_bst_ref);
if (*is_bst_ref == 1 && node->data > *max_ref)
left_flag = true;
/* Before updating *min_ref, store the min value in left subtree. So that we
have the correct minimum value for this subtree */
min = *min_ref;
/* The following recursive call does similar (similar to left subtree)
task for right subtree */
*min_ref = INT_MAX;
rs = largestBSTUtil(node->right, min_ref, max_ref, max_size_ref, is_bst_ref);
if (*is_bst_ref == 1 && node->data < *min_ref)
right_flag = true;
// Update min and max values for the parent recursive calls
if (min < *min_ref)
*min_ref = min;
if (node->data < *min_ref) // For leaf nodes
*min_ref = node->data;
if (node->data > *max_ref)
*max_ref = node->data;
/* If both left and right subtrees are BST. And left and right
subtree properties hold for this node, then this tree is BST.
So return the size of this tree */
if(left_flag && right_flag)
{
if (ls + rs + 1 > *max_size_ref)
*max_size_ref = ls + rs + 1;
return ls + rs + 1;
}
else
{
//Since this subtree is not BST, set is_bst flag for parent calls
*is_bst_ref = 0;
return 0;
}
}
@ BVarghese
We have to take largest continuous increasing sequence (LCIS) and not largest increasing sequence(LIS). And for this we don't have to use DP. It can be done by a single pass by maintaining two variables, one keeping the record of start of the largest sequence and the other keeping the record of the length of the largest sequence...
So, the total time complexity will be O(n) for inorder and O(n) for LCIS making a total of O(n)..
node *findlargestbst(node *proot) {
node *pnode;
findlargestbstrecursive(proot, &pnode);
return pnode;
}
unsigned int findlargestbstrecursive(node *proot, node **ppnode) {
assert(ppnode);
// Look for NULL node or leaf node
if (!proot || (!proot->left && !proot->right) {
*ppnode = proot;
return proot ? 1 : 0;
}
node *prleft, *prright;
unsigned int lleft, lright;
lleft = findlargestbstrecursive(proot->left, &prleft);
lright = findlargestbstrecursive(proot->right, &prright);
if ((prleft == proot->left) && (prright == proot->right)) {
// All the subtrees are BST, check to see if current node is also a part of valid BST
if (((!prleft) || (prleft->data < proot->data)) &&
((!prright) || (prright->data > proot->data))) {
// proot is part of the larger BST
*ppnode = proot;
// increment the height and return to caller
return lleft > lright ? lleft + 1 : lright + 1;
}
}
// Compare the lengths of subtrees and pass the correct root to caller
*ppnode = lleft > lright ? prleft : prright;
// Cannot increase height since current node is not part of BST.
return lleft > lright ? lleft : lright;
Recursion. Given a node n, the method returns a BST object, which contains the node as well as the size of the largest BST under node n. We then check whether the BST under left child is the left child itself and whether the BST under right child is the right child itself. If so, we check whether the current node has value larger than left node and smaller than right node. If so, return the current node as largest BST. Otherwise, return the BST that has a larger size.
class Node {
int value;
Node left;
Node right;
}
class BST {
Node node;
int size;
public BST(Node node, int size) {
this.node = node;
this.size = size;
}
}
class LargestBST {
static BST largestBST(Node n) {
if(n == null)
return new BST(null, 0);
BST leftLargest = largestBST(n.left);
BST rightLargest = largestBST(n.right);
if(leftLargest.node == n.left && rightLargest.node == n.right
&& (n.left == null || n.value >= n.left.value)
&& (n.right == null || n.value <= n.right.value)) {
return new BST(n, 1 + leftLargest.size + rightLargest.size);
} else if(leftLargest.size > rightLargest.size) {
return leftLargest;
} else {
return rightLargest;
}
}
}
public void findBSST(){
findBSSti(root);
}
private int findBSSti(Node n) {
if(n == null) return 0;
boolean btFound = false;
int l = -1,r = -1;
if(n.left != null){
l = findBSSti(n.left);
}else{
l = 0;
}
if(n.right != null){
r = findBSSti(n.right);
}else{
r = 0;
}
if (l >=0 && r >= 0){
if(n.left != null){
btFound = (n.left.value < n.value);
}else{
btFound = true;
}
}
if(btFound){
if(n.right != null){
btFound = (n.right.value > n.value);
}else{
btFound =true;
}
}
if(btFound){
int ret = -1;
ret = (l > r)? (l+1):(r+1);
if(ret > count){
count = ret;
bstNode = n;
}
return ret;
}else{
return -1;
}
}
What is "count " in your program and where you are initializing it.
Can you explain you algorithm??
Sure, Count and bstNode are class members. they are initialized in constructor as
-1 and null.
Explanation -
for a node which do not have right or left child we are returning depth 1 which means that this is a binary tree of depth 1. This is the base case.
We build on this as follows
For every node which have not null children we are trying to see if binary search tree property holds for it if so, we are returning whatever count is bigger left one or the right one. (simply the depth of binary search trees rooted at left and right child)
If at any point a tree is not binary tree we are returning -1 for that node.
At any point if we encounter a bst which is greater than in depth than earlier encountered binary tree we set the class members.
Hope it helps
largest = None
max_node_count = 0
def largest_bst(root, allowed_min, allowed_max):
global largest, max_node_count
if root == None:
return 0, None
if allowed_min < root.key < allowed_max:
leftnodes, left_child = largest_bst(root.left, allowed_min, root.key)
rightnodes, right_child = largest_bst(root.right, root.key, allowed_max)
p = Node(root.key)
p.left = left_child
p.right = right_child
if leftnodes + rightnodes + 1 > max_node_count:
max_node_count = leftnodes + rightnodes + 1
largest = p
return leftnodes + rightnodes + 1, p
else:
_, _ = largest_bst(root, -sys.maxint, sys.maxint)
return 0, None
@BVarghese, good one but i think we can not get the actual structure of the BST which resides in the given binary tree using inorder traversed increasing sequence, isn't it ?
@ BVarghese
- shekhar2010us June 26, 2013We have to take largest continuous increasing sequence (LCIS) and not largest increasing sequence(LIS). And for this we don't have to use DP. It can be done by a single pass by maintaining two variables, one keeping the record of start of the largest sequence and the other keeping the record of the length of the largest sequence...
So, the total time complexity will be O(n) for inorder and O(n) for LCIS making a total of O(n)..