Google Interview - Kth Smallest Element in BST

Given a binary search tree and an integer K, find K-th smallest element in BST.

For example: 
Input:

   2
  / \
 1   3

K = 2

Output:
2

Note: Your solution musb be in-place without altering the nodes' values.

 

Solution 1:

in-order递归访问。

TreeNode* kth_smallest(TreeNode* root, int& k) {
    if(!root || k < 0 ) return nullptr;
    TreeNode* left = kth_smallest(root->left, k);
    if(left) return left;
    if(--k == 0) return root;
    return kth_smallest(root->right, k);
}

 

Solution 2:

in-order非递归访问。

TreeNode* kth_smallest(TreeNode* root, int& k) {
    if(!root || k <= 0 ) return nullptr;
    TreeNode* node = root;
    stack<TreeNode *> st;
    while(!st.empty() || node) {
        if(node) {
            st.push(node);
            node = node->left;
        } else {
            TreeNode *p = st.top();
            st.pop();
            if(--k == 0) return p;
            if(p->right) node=p->right;
        }
    }
    return nullptr;
}