Энный самый большой элемент в дереве двоичного поиска

Подсказка: используйте для обхода дерева. Он может распечатать элементы в отсортированном порядке, так что вы обязательно найдете N-й по величине элемент. Во время «прогулки» ведите счетчик, увеличиваясь каждый раз, когда вы «посещаете» узел.

Редактировать : хотя ответ IVlad действительно быстрее, он требует, чтобы вы сохраняли дополнительную информацию в узлах. Этот ответ - нет, но это O (n) . Просто укажите, что это компромисс, о котором вы должны знать.

Используйте инвертированный упорядоченный трансверсаль, то есть сначала переходите к правому ребенку, а не к левому. Рекурсивно это можно получить следующим образом: Самый важный вопрос, что при рекурсивном решении необходимо использовать глобальный счетчик.

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

Решение на 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);
    }
}