Nth largest element in a binary search tree

Question

How to find the Nth largest node in a BST?

Do I keep a count variable while doing In Order Traversal of a BST? Return the element when the count = N???

Answer 1

Hint: use inorder traversal of the tree. It can print out the items in sorted order, so you can sure find the Nth largest item. Keep a counter as you "walk", incrementing each time you "visit" a node.

Edit: while IVlad's answer is indeed faster, it requires you to keep extra information in the nodes. This answer doesn't but it's O(n). Just pointing out that this is a tradeoff you have to be aware of.

Answer 2

See my answer here. You can do this in O(log n) on average where n = number of nodes. Worst case is still O(n) IF the tree isn't balanced (always O(log n) if it is balanced however). In order traversal is always O(n) however.

Answer 3

Use a inverted inorder tranversal.that is go to right child first instead of left child. recursively this can be obtained as follows: The most important issue that a global count must be used when considering recursive solution.

reverseInorder(root){
 if(root!=null){
reverseInorder(root->rightChild);
self
reverseInorder(root->leftChild);
}
}

Solution in java

    package datastructure.binaryTree;

import datastructure.nodes.BinaryTreeNode;


public class NthElementFromEnd {
    private BinaryTree tree=null;
    int currCount=0;
    public NthElementFromEnd(int[] dataArray) {
        this.tree=new BinaryTree(dataArray);

    }
    private void getElementFromEnd(int n){
        getElementFromEnd(this.tree.getRoot(),n);
    }
    private void getElementFromEnd(BinaryTreeNode node,int n){
        if(node!=null){
            if(currCount<n)
            getElementFromEnd(node.getRightChild(),n);
            currCount++;

            if(currCount==n)
            {
                System.out.print(" "+node.getData());
                return;
            }
            if(currCount<n)
            getElementFromEnd(node.getLeftChild(),n);
        }
    }

    public static void main(String args[]){
        int data[]={1,2,3,4,5,6,7,8,9};
        int n=2;
        new NthElementFromEnd(data).getElementFromEnd(n);
    }
}

Answer 4

the above worked...