2
votes

Can we find the kth largest element using inorder traversal without knowing the height of the binary search tree? Or is there a way where we make a new pattern of traversal like "RIGHT ROOT LEFT"

3
If your question is can we run through a binary decision tree by doing right then left instead of drilling down, look for breath first search - Mayeul sgc
just do an inorder traversal backwards. Note, however, that if you're in a job interview and the interviewer asks you how to find the Kth largest element in a BST, he's gonna want to know how you can make it work in log(N) time. - Matt Timmermans
Thanks for the comments i have found some way to get it done with "RIGHT ROOT LEFT" traversal pattern - Adithya Sai

3 Answers

1
votes

Can we find the kth largest element using inorder traversal without knowing the height of the binary search tree?

Yes we can.

We can do that using some extra space. We do not necessarily need to do RIGHT-ROOT-LEFT to find out kth largest element (Although doing so would avoid usage of extra space).

There are several approaches.

The most basic one is to have a queue.

Whenever you are traversing inorder-ly, keep inserting the values in the queue. Needless to say, as it is a binary search tree, the queue will be sorted. Thus the kth largest element is at queue.size() - 1 - k index. (Assuming that 0th largrst is the maximum element, 1st largest is 2nd maximum and so on) This approach would require O(n) extra space regardless of k

To optimize the space used, we can use the information about k
Note that we only need element at (queue.size() - 1 - k)th index. Thus we can have a queue of size (k+1). Before inserting an element, we will check if the queue has more than k element, if it has, we would remove one element from front as we do not require it.
After the traversal is done, the kth largest element would be at the front of the queue.

Here is the java implementation of both the approaches :

import java.util.LinkedList;
import java.util.Queue;

class Node {
    int data;
    Node left;
    Node right;

    static Queue<Integer> efficient = new LinkedList<>();
    static Queue<Integer> complete = new LinkedList<>();

    Node(int n) {
        this.data = n;
        this.left = null;
        this.right = null;
    }

    public static void inorder(Node node, int k) {
        if (node == null) {
            return;
        }
        inorder(node.left, k);
        if (efficient.size() > k) {
            efficient.poll();
        }
        efficient.add(node.data);
        complete.add(node.data);
        System.out.println(efficient.toString());
        inorder(node.right, k);
    }

    public static void main(String[] args) {
        Node root = new Node(7);
        root.left = new Node(4);
        root.left.left = new Node(1);
        root.left.right = new Node(5);
        root.left.right.right = new Node(6);
        root.right = new Node(9);
        int k = 2;
        inorder(root, k);
        System.out.println("Efficient queue size : " + efficient.size() + " " + efficient.peek());
        System.out.println("Full queue size : " + complete.size() + " " + complete.toArray()[complete.size() - 1 - k]);

    }

}

Run this and you will know how efficient queue grows.

Please note that here, k should be less than the number of nodes in the tree. If it is not, then the answer would be the smallest element.

Other approaches uses a heap for more general solution. In such cases the tree is not required to be a binary search tree.

1
votes

What about this:

  • let x be the node corresponding to the minimum element of the tree (e.g. x = T.root; while (x->right != NULL) { x = x->right; })
  • Now repeat x = x.predecessor() k-1 times (obviously, take care of edge case)
  • return x (you've found the k-th largest element in the tree)

Implementing predecessor and successor methods on a BST isn't hard, and it's easy when nodes have an additional pointer to parent node.

0
votes

Are you talking about a simple binary tree or any tree like AVL tree?

If I understand correctly, you don't need to know the height at all... Inorder traversal - RIGHT ROOT LEFT - is supposed to go from the highest value to the lowest.

Each time you enter the function, you may increase a static variable(or send another argument to the function) - until you get to K.

You may also maintain a degree tree, and know directly where to go through that tree.