Amazon Interview Question Software Engineer / Developers
Country: India
Interview Type: In-Person
In case of complete bst we can utilize the property of having n depth and 2^n-1 elements as :
int getnode(struct tnode *root,int n,int k)
{
if(root==NULL)
return -1;
if(n/2 +1 == k)
return root->val;
if(n/2 + 1 > k)
return getnode(root->left,n/2,k);
return getnode(root->right,n/2,k-n/2-1);
}
n here is total nodes in tree
You can augment the BST where each node will store the size of the left sub-tree as well as the size of the right sub-tree. So at each node if N>size(left_sub-tree) traverse the right sub-tree. Otherwise traverse the left sub-tree. If you go to the right sub-tree then you'll have change N to N - size(left_sub-tree) -1 .
Just some random thoughts:-
As its given that BST is balanced, we can follow below approach:-
1)Find the depth(logn), let n is depth, call a function foo on root and pass depth as well
foo(root, n, k)
2)Total no of element is 2^n -1, no of nodes in left and right subtree each is 2^(n-1) - 1
3)if k = 2^(n-1), you found the ans, return the current node
4)else if k > 2^(n-1), search in right subtree foo(root.right, n-1, k - 2^(n-1))
5)else search in left subtree, foo(root.right, n-1, k )
Let me know if you see any issue in approach.
Exactly my thought, yet it it works only when the tree is a full binary sort tree. This is code in C++:
TreeNode* getNthNodeOfFullBST(int n, TreeNode* p, int height, TreeNode* parent, int parentIndex)
{
//get the order of node p
int index = p == parent->left ? parentIndex - (1 << height) : parentIndex + (1 << height);
if(index == n) return p;
return getNthNodeOfFullBST(n, n > index ? p->right : p->left, height - 1, p, index);
}
TreeNode* getNthNodeOfFullBST(TreeNode* pFullBST, int n)
{
if(n < 1 || pFullBST == NULL) return NULL;
//get height of the full BST
int height = 0;
TreeNode* p = pFullBST;
for(; p->left != NULL; p = p->left) ++height;
if(n > (1 << (height + 1))) return NULL;//there are less than n nodes at all
//get the order of root
int index = 1 << height;
if(n == index) return pFullBST;
return getNthNode(n, n > index ? pFullBST->right : pFullBST->left, height - 1, pFullBST, index);
}
Damn you guys were quicker ;-)
public class TreeLookup<T extends Comparable<T>> {
public T determineNthElement(final Node<T> root, final int nThElementPosition) {
T retVal = null;
if (root != null) {
retVal = determineNthElement(root, nThElementPosition, determineTreeHeight(root));
}
return retVal;
}
private T determineNthElement(final Node<T> root, final int nThElementPosition, final int treeHeight) {
final int singleBranchChildCount = ((int)Math.pow(2, treeHeight) - 2) / 2;
T retVal = null;
if ((singleBranchChildCount == 1 && (singleBranchChildCount) == nThElementPosition) ||
(singleBranchChildCount != 1 && (singleBranchChildCount + 1) == nThElementPosition)) {
retVal = root.getValue();
} else {
if (singleBranchChildCount >= nThElementPosition) {
retVal = determineNthElement(root.getLeft(), nThElementPosition-1, treeHeight-1);
} else {
retVal = determineNthElement(root.getRight(), nThElementPosition-1, treeHeight-1);
}
}
return retVal;
}
private final int determineTreeHeight(Node<T> root) {
int height = 1;
while (root.getLeft() != null) {
root = root.getLeft();
height++;
}
return height;
}
}
But this proof of concept (at least mine) don't work for all balanced tree. For this type of tree it will work:
15
8 20
6 10 18 22
type of tree it won't work:
15
8 20
6 10 18 22
9
Every time the search will only half the elements, so running time will be O(log(n))
You can hold this information in the node so totalChildUnderRootAtIndex() should run in O(1) time
Here is a code snippet.
public int findNthSmallest(int[] T, int n, int rootIndex)
{
if (n > T.length -1) {
return -1;
}
int totalLeftChildsAtRoot = totalChildUnderRootAtIndex(2*rootIndex,0,T);
int totalRightChildsAtRoot = totalChildUnderRootAtIndex(2*rootIndex+1,0,T);
if (n == totalLeftChildsAtRoot + 1) {
return T[rootIndex];
}
else if(n < totalLeftChildsAtRoot + 1)
{
//Search in left sub tree
return findNthSmallest(T, n, 2 * rootIndex);
}
else
{
//Search in teh right Sub Tree
return findNthSmallest(T, n-(totalLeftChildsAtRoot + 1), 2 * rootIndex+1);
}
}
public void visit(Node* root, int& number,int n) {
if(root == null) return;
visit(root->left,number,n);
if(number == n) {
cout<<root->value;
return;
}
number += 1;
visit(root->right,number,n);
}
int number = 0;
visit(root,number,3);
Not possible with a balanced bst. It is impossible to decide the path at root which to take in this case. It needs to be a complete bst instead for a O(lgn) solution.
- Nitin May 01, 2014