Kth_Smallest_Element_in_a_BST.md

title	last_updated	keywords	sidebar	comments	permalink
leetcode- Kth Smallest Element in a BST	Dec 08, 2020	algorithm	mydoc_sidebar	true	Kth_Smallest_Element_in_a_BST.html

#. Problem

Kth Smallest Element in a BST

1. My approach

I got none.

2. Recursive Inorder Traversal

Applying in-order traversal was an interesting approach which works well. So I recursively made a vector of int and return the k th element.

w/ Global variable

class Solution {
    // v as a global variable
    vector<int> v;
public:
    void inorder(TreeNode* root){
        if(not root) return;
        
        if(root->left) inorder(root->left);
        v.push_back(root->val);
        if(root->right) inorder(root->right);
    }
    
    int kthSmallest(TreeNode* root, int k) {
        inorder(root);        
        return v[k-1];
    }
};

w/o Global variable

class Solution {
public:
	// use v as a reference parameter
    void inorder(TreeNode* root, vector<int>& v){
        if(not root) return;
        
        if(root->left) inorder(root->left, v);
        v.push_back(root->val);
        if(root->right) inorder(root->right, v);
    }
    
    int kthSmallest(TreeNode* root, int k) {
        vector<int> v;
        inorder(root, v);        
        return v[k-1];
    }
};

Interestingly enough, using reference parameter gives better performance. I guess referring a global variable is no better than passing by references.

	Time	Space
w/ global variable	40 ms	24.8 MB
w/o global variable	20 ms	24.8 MB

3. Iterative Inorder Traversal

It should have the same time complexity except it returns it right after it finds the target. Even with that, the worst case would take the same time. I just wanted to add this so that I could think about the algorithm, since I didn't come up with it.

class Solution {
public:
    int kthSmallest(TreeNode* root, int k) {
        stack<TreeNode*> s;
        
        while(true){
            while(root != NULL){
            	// go left all the way to the end 
                s.push(root);
                root = root->left;
            }
            // and check it if it's k th
            root = s.top();
            s.pop();
            if(--k == 0) return root->val;
            // and see it's right tree
            root = root->right;
        }
    }
};

It's better with pics (here)

Time	Memory
20 ms	24.6 MB

4. Epilogue

What I've learned from this exercise:

• Inorder traversal could be used to get an ordered array.
• How to get inorder traversal iteratively.