Nth largest element in a binary search tree

How to find the Nth largest node in a BST?

Do I keep a count variable while doing In Order Traversal of a BST? Ret开发者_StackOverflow社区urn the element when the count = N???

The idea is very simple: traverse the tree in decreasing order of the values of each node. When you reach the Nth node, print that node value. Here is the recursive code.

void printNthNode(Node* root, int N)
{
   if(root == NULL)
       return;

   static int index = 0; //These will initialize to zero only once as its static

   //For every Node go to the right of that node first.
   printNthNode(root->right, N);


   //Right has returned and now current node will be greatest
   if(++index == N)
   {
    printf("%d\n", root->data);
    return;
   }

   //And at last go to the left
   printNthNode(root->left, N);
}

Edit - As per the comments below, looks like this is one-time call function due to the static local variable. This can be solved by passing wrapper object for index as follows:

    class WrapIndex {
         public: int index;
    };

and method signature would change to

void printNthNode(Node* root, int N, WrapIndex wrapInd)

Now, we don't need a local static variable; instead use index of the wrapper object. The call would look like

WrapIndex wrapInd = new WrapIndex();
wrapInd.index=0;
printNthNode(root,7,wrapInd);

wrapInd.index=0;
printNthNode(root,2,wrapInd);

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.

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.

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);
    }
}

int nLargeBST(node *root, int N) {
    if (!root || N < 0) {
        return -1;
    }
    nLargeBST(root->left, N);
    --N;
    if(N == 0) {
        return root->val;
    }
    nLargeBST(root->right, N);
}

This piece of code is from my assignment and one of the condition was not to use arrays. In order to make the code more compact and readable you can use stringName.split("|"). Since the method is recursive I use the stringBuilder which has the following structure: "counter|orderOfElementToFind|dataInrequiredNode"

protected StringBuilder t(StringBuilder s)
{
    if (lc != null) 
    {
        lc.t(s);
}


if((s.toString().charAt(s.toString().length() - 1)) == '|')
{
        String str = s.toString();
    s.delete(0, s.length());

        int counter = 0, k = 0;


        String strTemp = "", newStrBuilContent = "";

        for (int i = 0, c = 0 ; i < str.length(); ++i)
        {
            if (c == 0)
            {
            if (str.charAt(i) != '|')
    {
        strTemp += str.charAt(i); 
    }
    else
    {
        counter = Integer.parseInt(strTemp);
        ++c;

        strTemp = "";
    }
            }
    else
    {

            if (str.charAt(i) != '|')
        {
            strTemp += str.charAt(i); 
            }
        else
        {
                k = Integer.parseInt(strTemp);
        }

    }

    counter ++;

            newStrBuilContent = (counter + "|" + k + "|");
    s.append(newStrBuilContent);
    if (counter == k)
    {
        double ldata = this.getData();
        s.append(ldata);

    }

}

if (rc != null) 
{
    rc.t(s);
} 

    return s;

}

and the method call:

// the value of counter ad the beginning is 0 and data 
// segment is missing
String s = ("0|" + order +"|");
StringBuilder strBldr = new StringBuilder(s); 
String content = sTree.t(strBldr).toString();

s = "";

for (int i = 0, c = 0; i < content.length(); ++i)
{           
    if (c < 2)
{
    if (content.charAt(i) == '|')
    {  
        ++c;
        }
    }
else
{
    s += content.charAt(i);
}
}
    `

• Maintain size of subtree at eachnode(root.size some thing like that). for example {2,3,1} is a binary tree with root 2 then the size of node (2) is 3, node (1) size is 1, and node (2) size is 1

• if u want to find 4 th larget element in the tree with root node size 23 , think about its rank

• the max element rank is 23, because the root node size is 23. so 4 th largest element rank is 23-4+1= 20

• so we have to find 20th rank element in the given tree

• initially declare a rank=0 flag to zero

• starting from root node find its rank (rank+ size of left child + 1) for example left child size is 16 then root element rank is 17(rank+size of left child +1)

• so we have to look for the element with the rank 20. so obviously we have to traverse to its right child

• traverse to right child and based on above formula find right child rank(based on above formula, note: now rank flag value is is 17),decide whether to go right or left based on the rank

• repeat this process recursevely untill we found rank==20

I would do it by going though the tree from biggest to smallest element and returning value when asked position is reached. I implemented similar task for second largest value. Value of 2 is hardcoded, but is it easy to change with additional parameter :)

void BTree::findSecondLargestValueUtil(Node* r, int &c, int &v)
{
    if(r->right) {
        this->findSecondLargestValueUtil(r->right, c, v);
    }

    c++;

    if(c==2) {
        v = r->value;
        return;
    }

    if(r->left) {
        this->findSecondLargestValueUtil(r->left, c, v);
    }
}


int BTree::findSecondLargestValue()
{
    int c = 0;
    int v = -1;

    this->findSecondLargestValueUtil(this->root, c, v);

    return v;
}

// C++ program to find k'th largest element in BST
#include<iostream>
using namespace std;

struct Node
{
    int key;
    Node *left, *right;
};

// A utility function to create a new BST node
Node *newNode(int item)
{
    Node *temp = new Node;
    temp->key = item;
    temp->left = temp->right = NULL;
    return temp;
}

// A function to find k'th largest element in a given tree.
void kthLargestUtil(Node *root, int k, int &c)
{
    // Base cases, the second condition is important to
    // avoid unnecessary recursive calls
    if (root == NULL || c >= k)
        return;

    // Follow reverse inorder traversal so that the
    // largest element is visited first
    kthLargestUtil(root->right, k, c);

    // Increment count of visited nodes
    c++;

    // If c becomes k now, then this is the k'th largest 
    if (c == k)
    {
        cout << "K'th largest element is "
             << root->key << endl;
        return;
    }

    // Recur for left subtree
    kthLargestUtil(root->left, k, c);
}

// Function to find k'th largest element
void kthLargest(Node *root, int k)
{
    // Initialize count of nodes visited as 0
    int c = 0;

    // Note that c is passed by reference
    kthLargestUtil(root, k, c);
}

/* A utility function to insert a new node with given key in BST */
Node* insert(Node* node, int key)
{
    /* If the tree is empty, return a new node */
    if (node == NULL) return newNode(key);

    /* Otherwise, recur down the tree */
    if (key < node->key)
        node->left  = insert(node->left, key);
    else if (key > node->key)
        node->right = insert(node->right, key);

    /* return the (unchanged) node pointer */
    return node;
}

// Driver Program to test above functions
int main()
{
    /* Let us create following BST
              50
           /     \
          30      70
         /  \    /  \
       20   40  60   80 */
    Node *root = NULL;
    root = insert(root, 50);
    insert(root, 30);
    insert(root, 20);
    insert(root, 40);
    insert(root, 70);
    insert(root, 60);
    insert(root, 80);

    int c = 0;
    for (int k=1; k<=7; k++)
        kthLargest(root, k);

    return 0;
}

Swift version. This follows closely with what Vallabh Patade said. The counter is increased by 1 when it tries to go through a node that has no child though. A bit different than his.

class BinaryNode {
    var val: Int
    var left: BinaryNode?
    var right: BinaryNode?

    init(value: Int) {
        self.val = value
    }
}

func findMaxValue(_ n: Int, from root: BinaryNode?) {
    var counter = 0
    maxValue(counter: &counter, n: n, node: root)
}

private func maxValue(counter: inout Int, n: Int, node: BinaryNode?) {
    if node == nil {
        counter += 1
        return
    }
    maxValue(counter: &counter, n: n, node: node?.right)
    // If the counter has reached the nth node we're looking for.
    if counter == n {
        if let val = node?.val { print(val) }
    }
    maxValue(counter: &counter, n: n, node: node?.left)
}

Here is how you can do this by a slight modification of the in-order traversal of the binary search tree - we are finding the kth largest element;

    void kthLargest(Node node, int k, int count) {

      if(node != null) {

         nthLargest(node.left,k,count); //traversing the left node

         //while visit the node we do the following
         count++; // increment the count and check if that is equal to k
         if ( count == k ) {
           System.out.println("Node found "+node.value);
         } 

         nthLargest(node.right,k,count); //traversing the right node
      }

    }

But the problem in this way you are going to reach the kth smallest element and hence you method call should be this: as kth largest element = (n-k)th smallest element.

    nthLargest(root,n-k,0);

K’th Largest Element in BST . Learn how to think for such problem and solve with recursion . Kth Larget Explanation Recursion