KthElementInBST.cpp

/*
http://www.careercup.com/question?id=15645665
Find the k'th largest element in a binary search tree.
*/
#include <stack>
#include <iostream>
using namespace std;

struct Node {
    int val;
    struct Node *left;
    struct Node *right;
    Node(int _val) {
        val = _val;
        left = NULL;
        right = NULL;
    }
};

stack<Node*> stak;
Node* current = NULL;

Node* forward() {
    while (current != NULL || !stak.empty()) {
        if (current != NULL) {
            stak.push(current);
            current = current ->left;
        } else { // stack not null
            Node* ret = stak.top();
            stak.pop();
            current = ret->right;
            return ret;
        }
    }
    return NULL;
}

Node * kth_largest(Node *root, int k) {
    current = root;
    Node * ret = NULL;
    for (int i = 0; i < k; i++) {
        ret = forward();
    }
    return ret;
}

int main() {
    Node * root = new Node(5);
    root->left = new Node(3);
    root->right = new Node(6);
    Node * tmp = root->left;
    tmp->left = new Node(1);
    tmp->right = new Node(4);
    tmp = tmp->left;
    tmp->right = new Node(2);
    tmp = root->right;
    tmp->right = new Node(8);
    tmp = tmp->right;
    tmp->left = new Node(7);
    tmp->right = new Node(10);
    tmp->right->left = new Node(9);
    for (int i = 1; i <= 10; i++) {
        Node * ret = kth_largest(root, i);
        cout << ret->val << endl;
    }

    system("pause");
}