Amazon Interview Question Software Engineer / Developers
Country: India
Interview Type: Phone Interview
We can do reverse inorder traversal of a BST in order to obtain kth largest element, by keeping global variable count for number of elements seen so far.
Other method would be to use order statistics on BST, i.e. to store count of nodes in left subtree and right subtree in a node.
in order traversal where larger child comes first. take an iterative approach so that we can break early
public static V kthLargest(BinaryTree<V> root, int k) {
Stack<BinaryTree<V>> stack = new Stack<BinaryTree<V>>();
BinaryTree<V> node = root;
int i = 1;
V retval = root.key;
while(!stack.empty() || node != null) {
if(node != null) {
stack.push(node);
node = node.rightChild;
} else {
node = stack.pop();
retval = node.key;
if(i++ == k) break;
node = node.leftChild;
}
}
return retval;
}
// use morris transversal if we want O(1) space
stack<TreeNode*> s;
bool done = false, cnt = 0;;
while (!done)
{
while (root) { s.push(root); root = root->left; }
if (!s.empty())
{
++cnt;
if (cnt == k) return s.top();
root = s.top()->right; s.pop();
}
return NULL;
}
;
// Find Kth large Element in BST.
// 1. "Rev inorder" Traversal will Give desired result
// similarly we can get kth smallest Element using "Inorder traversal"
int BSTTree :: kthLarge (BSTNode* start, int k)
{
if (start != NULL)
{
kthLarge (start->right,k);
count ++;
if (count == k)
return start->data;
kthLarge (start->left,k);
}
}
Did u try out this code? This would work if you want to print the kth number(replacing return start->data with print). But function on the whole would not return the desired result.
recursive .. if a element is found it returns back to the calling function which is itself ..unnecessarily even after answer is found.
Unfortunately, the code would not be compiled.
int BSTTree :: kthLarge (BSTNode* start, int k)
{
if (start != NULL)
{
kthLarge (start->right,k);
count ++;
if (count == k)
return start->data;
kthLarge (start->left,k);
// Function must return a value here!!!
}
// Function must return a value here!!!
}
- Sani October 27, 2011// Return pointer to the kth largest Node* kthlargest(Node* root, int &k) { if( root == NULL ) return NULL; else { Node* result = kthlargest(root->right, int k); if( result ) return result; k--; if( k == 0 ) return root; return kthlargest(root->left, k); } }