Walmart Labs Interview Question
Applications DevelopersCountry: India
Interview Type: In-Person
A simple inorder traversal should work here. In the current implementation there are two methods with the same signature but different return types. I'm not a Java person but this looks like trouble.
This is what I lashed up in C++:
template <typename T>
struct Node
{
Node<T>* Left;
Node<T>* Right;
T Value;
};
template <typename T>
static const Node<T>*
GetKthSmallestWorker(const Node<T>* node, int& k)
{
const Node* found = nullptr;
if (node->Left)
{
found = GetKthSmallestWorker(node->Left, k);
}
if (nullptr == found)
{
if (--k == 0)
{
found = node;
}
else if (Node->right)
{
found = GetKthSmallestWorker(Node->Right, k);
}
}
return found;
}
template <typename T>
Node<T>*
GetKthSmallest(const Node<T>& node, int k)
{
return (k > 0) ? GetKthSmallestWorker(&node, k) : nullptr;
}
Assuming that nodes in the BST hold counters for the number of elements in each of its subtrees. This is pretty much the approach zortlord presented but did not code.
In C:
int kth(Node *p, int k)
{
if (!p)
return ERROR;
if (k == p->left_count+1)
return p->element;
if (k <= p->left_count) {
return kth(p->left, k);
}
else {
return kth(p->right, k - p->left_count - 1);
}
}
Doing inorder traversal and keeping a counter for kth min number
int smallest=0;
void kthNode(treeNode *head, int k)
{
static int counter = 0;
if (!head || (k < 0))
return;
kthNode(head->left, k);
counter++;
if (k == counter) {
smallest = head->data;
return;
}
kthNode(head->right, k);
}
Just implemented below logic given in stackoverflow:
Let each node in the BST have a field that returns the number of elements in its left and right subtree. Let the left subtree of node T contain only elements smaller than T and the right subtree only elements larger than or equal to T.
Now, suppose we are at node T:
k == num_elements(left subtree of T), then the answer we're looking for is the value in node T
k > num_elements(left subtree of T) then obviously we can ignore the left subtree, because those elements will also be smaller than the kth smallest. So, we reduce the problem to finding the k - num_elements(left subtree of T) smallest element of the right subtree.
k < num_elements(left subtree of T), then the kth smallest is somewhere in the left subtree, so we reduce the problem to finding the kth smallest element in the left subtree.
int total(treeNode *head)
{
if (!head)
return 0;
return 1 + total(head->left) + total(head->right);
}
void kthNode(treeNode *head, int k)
{
int to;
if (k < 0 || !head) {
printf("couldn't find it\n");
return;
}
if (k == 0) {
printf("got it%d\n", head->data);
return;
}
to = total(head->left);
if ((to+1) == k) {
printf("found the rising star %d\n", head->data);
return;
}
if ((to+1) > k)
kthNode(head->left, k);
else
kthNode(head->right, k-(to+1));
}
Doubt that a O(log n) solution can be given for this problem, unless the BST is balanced probably?
Worst case, take a BST that is build completely with just the right tree
Example:
1
2
3
4
5
6
In order to find the 6th element, we have to traverse through down the right chain and we will have a complexity of O(n).
int count;
int main()
{
int K;
printf( "Enter value of K \n");
scanf ("%d", &K);
count = k;
inorder(head);
}
void inorder( struct node *head)
{
if(head == NULL)
return ;
inorder(head->left);
count --;
if (count == 0)
{
printf("Kth smallest element = %d ", head->data);
return;
}
inorder(head->right);
}
The question has certain amount of uncertainty/ambiguity. It is actually pretty good question if the goal is to trigger the discussion to resolve that.
For instance, O(log(N)) possible when tree is balanced and one of the following condition is met
a) k << N, so we can use in-order traversal
b) each node store the count of nodes in the subtree rooted by the node, so we can find kth element recursively.
Recursive approach
public int findSmallest(int k) {
return findSmallest(root, k);
}
private int size(BSTNode node) {
if (node != null) {
return 1 + size(node.getLeft()) + size(node.getRight());
}
return 0;
}
private int findSmallest(BSTNode node, int k) {
int count;
count = size(node.getLeft()) + 1;
if (count== k) {
return node.getData();
}
if(count > k){
return findSmallest(node.getLeft(),k);
}else{
return findSmallest(node.getRight(),k-count);
}
}
We can keep track of the elements in a subtree of any node while building the tree. As we have to find the kth smallest element so we can maintain the no. of elements in the subtree of a node. Even we have to maintain the no. of element in the left subtree only.
Let us assume that root is having x elements in its left subtree then
1) if k=x+1 ,then root is kth smallest element.
2)if k<x ,we continue our search in the left subtree.
3)if k>x+1 , then we have to find (k-x-1)th element in the right subtree of the root.
here is a c code implementation of O(logn):
int k_smallest_element(node_t *root, int k)
{
int ret = -1;
if( root )
{
node_t *pTraverse = root;
while(pTraverse)
{
if( (pTraverse->lCount + 1) == k )
{
ret = pTraverse->data;
break;
}
else if( k > pTraverse->lCount )
{
k = k - (pTraverse->lCount + 1);
pTraverse = pTraverse->right;
}
else
{
pTraverse = pTraverse->left;
}
}
}
return ret;
}
We can keep track of the elements in a subtree of any node while building the tree. As we have to find the kth smallest element so we can maintain the no. of elements in the subtree of a node. Even we have to maintain the no. of element in the left subtree only.
Let us assume that root is having x elements in its left subtree then
1) if k=x+1 ,then root is kth smallest element.
2)if k<x ,we continue our search in the left subtree.
3)if k>x+1 , then we have to find (k-x-1)th element in the right subtree of the root.
here is a c code implementation of O(logn):
int k_smallest_element(node_t *root, int k)
{
int ret = -1;
if( root )
{
node_t *pTraverse = root;
while(pTraverse)
{
if( (pTraverse->lCount + 1) == k )
{
ret = pTraverse->data;
break;
}
else if( k > pTraverse->lCount )
{
k = k - (pTraverse->lCount + 1);
pTraverse = pTraverse->right;
}
else
{
pTraverse = pTraverse->left;
}
}
}
return ret;
}
If you have a tree that stores the height of each branch, then you can use that information to locate the Kth element by simply traversing to the Kth element in the tree. This would take only O(log n) operations. However, most tree implementations do not store height information so this operation can be done in O(log n + k) time by traversing the tree to the smallest element and then navigating the tree until you find the k th item. I've implemented the second approach below:
- zortlord December 04, 2014