Share my C++ solution,easy to understand And offer pseudo-code of O(height of BST)


  • 0
    V
    class Solution {
    public:
        int kthSmallest(TreeNode* root, int k) {
            if (root == NULL)
                return INT_MAX;
            
            stack<TreeNode*> s;
            TreeNode *temp = root;
            
            while (!s.empty() || temp != NULL)
            {
                while (temp != NULL)
                {
                    s.push(temp);
                    temp = temp->left;
                }
                
                temp = s.top();
                k--;
                if (k == 0)
                    return temp->val;
                    
                s.pop();
                temp = temp->right;
            }
            
            return INT_MIN;
        }
    };

  • 5
    V

    O(height of BST) Solution:

    if we could modify the BST node's structure,like following:
    
    struct TreeNode {
        int val;
        int leftTotal;//the total nodes in the left subtree
        TreeNode *left;
        TreeNode *right;
        TreeNode(int x) : val(x), left(NULL), right(NULL) {}
    };
    
    Then we can get the optimal runtime complexity : O(height of BST).
    Of course we should compute 'leftTotal' when we establish the BST or Traversing the BST beforehand.
    The pseudo-code:
    
     1. if k == (currentNode->leftTotal + 1), return;
    
     2. else if k > (currentNode->leftTotal + 1), let k = k - (currentNode->leftTotal + 1) and currentNode = currentNode->right;
    
     3. else currentNode = currentNode->left;

  • 0
    S

    When update the BST, we also need the 'rightTotal'. Or wehave to traverse the total BST each time after modifing the BST. Using 'rightTotal', the time complexity is O(H).

    Inserting or Deleting nodes, we have to update all nodes in the path of from the root to a leaf, which has been inserted or deleted. Deleting non-leaf nodes can transform to deleting leaf nodes.

    If modifing the BST is frequently, maintain these nodes will cost lots of time. So, this solution suites to less modifing situation.


  • 0
    J

    Why do we need a rightTotal? Don't we just need the leftTotal to determine the position of the Kth smallest element in O(H)?


Log in to reply
 

Looks like your connection to LeetCode Discuss was lost, please wait while we try to reconnect.