Amazon Interview Question Software Engineer / Developers
0of 0 votesGiven a binary search tree find the its least depth.
what if we also put few constraints in the recursive function-
int minBST(node * root)
{
if (node == NULL)
return 0;
elseif ( ! node->left && ! node->right ) // No child
return 1 ;
elseif ( ! node->left ) // Only right child,no left child
return ( 1+ minBST(root->right) );
elseif ( ! node->right ) // Only left child
return ( 1+ minBST(root->left) );
else
return 1 + min( minBST(root->left), minBST(root->right) );
}
I think this should work fine even if a tree only has left children Or only has right children. Because for the tree given by Anonimous,
20
30
40
For this tree- min height should be 3, and not 1.
Above approaches fail on the shown test case, one approach could be:
int count = 0;//denotes distance from the root
Do depth first traversal of tree(using a stack):
When you pop from the stack, read the nodes count, and push its children (right, left) in stack with value -> count + 1
If you have popped an node which has neither left nor right child, compare it to current min, if smaller, store it as min depth.
At the end, you will have the min depth of tree.
time complexity - O(no. of Vertex + no. of Edges)
worst case space complexity - O(V)
height(BST) = 1 + min(height(BST->left),height(BST->right));
- Anurag Singh February 11, 2011