Finding the $j^{th}$ Smallest Element in an AVL Tree

[evinda]

Hello! (Wave)

We consider an $\text{ AVL }$ tree $T$. At each node $v$ of the tree the number of nodes of the left subtree of $v$ is stored.
I want to write an algorithm that returns the $j^{th}$ smallest element of the tree in time $O(\log m)$ where $m$ is the number of nodes of the tree.

How could we do this? Could you give me a hint? (Thinking)

 

[evinda]

An $\text{ AVL } tree$ is a sorted binary tree. So the smallest element will be at the last level of the left subtree of the root, right? (Thinking)

 

[evinda]

We know that at each node $v$ of the tree, the number of nodes of the left subtree of $v$ is stored.
Does this mean that the number of nodes of the left subtree is the key or are there two fields? (Thinking)

 

[evinda]

I think that we could do it like that:

We check if the number of nodes of the left subtree of the root is smaller that $j-1$ and if this holds we know that the $j^{th}$ smallest element is at the left subtree of the root.
If the number of nodes of the left subtree of the root is equal to $j-1$, then we know that the root is the $j^{th}$ smallest element.
Otherwise, we know that we can find the desired element at the right subtree of the root.So if the root is not the $j^{th}$ smallest element , we will look at the nodes of the left/right subtree, till we find a node,of which the left subtree has $j-1$ elements.Am I right? (Thinking)

 

[johng1]

You haven't precisely specified an algorithm. Here's an implementation in C++:

class Node {
public:
  int key;
  int leftCount;
  Node* left;
  Node* right;
  Node();
};

Node* findKthSmallest(Node* p, int k) {
  int n = p->leftCount;
  if (n == k - 1) {
    return (p);
  }
  if (k <= n) {
    return (findKthSmallest(p->left, k));
  }
  return (findKthSmallest(p->right, k - n - 1));
}

 

[evinda]

You haven't precisely specified an algorithm. Here's an implementation in C++:

class Node {
public:
  int key;
  int leftCount;
  Node* left;
  Node* right;
  Node();
};

Node* findKthSmallest(Node* p, int k) {
  int n = p->leftCount;
  if (n == k - 1) {
    return (p);
  }
  if (k <= n) {
    return (findKthSmallest(p->left, k));
  }
  return (findKthSmallest(p->right, k - n - 1));
}

Could you maybe explain me why at this command: [m] return (findKthSmallest(p->right, k - n - 1)); [/m] the second argument is $k-n-1$?
Why are we looking for the $(k-n-1)^{th}$ smallest element of the right subtree? (Thinking)

 

[johng1]

Think of the keys in the tree as being 1,2, etc. Of course, this need not be the case but it's easier to think this way. As you originally pointed out, the kth smallest element in a list is characterized by there being k-1 elements in the list that are smaller. Now if the function gets to
return(findKthSmallest(p->right,k-n-1), it is true that there are n elements in the left subtree smaller than k;also k is not n+1. So in the right subtree, there are then k-n-1 elements smaller than k. That is in the right subtree we want the (k-n-1)th smallest element.
Maybe it would help if you traced the function for the following AVL tree (the 1st value in each node is the key: the 2nd value is leftCount):

 

[evinda]

Think of the keys in the tree as being 1,2, etc. Of course, this need not be the case but it's easier to think this way. As you originally pointed out, the kth smallest element in a list is characterized by there being k-1 elements in the list that are smaller. Now if the function gets to
return(findKthSmallest(p->right,k-n-1), it is true that there are n elements in the left subtree smaller than k;also k is not n+1. So in the right subtree, there are then k-n-1 elements smaller than k. That is in the right subtree we want the (k-n-1)th smallest element.
Maybe it would help if you traced the function for the following AVL tree (the 1st value in each node is the key: the 2nd value is leftCount):

Great! (Happy) Thanks a lot!