LeetCode Q230 K Smallest Node In BST

Given a binary search tree, write a function kthSmallest to find the kth smallest element in it.

Note: 
You may assume k is always valid, 1 ≤ k ≤ BST's total elements.

Follow up:
What if the BST is modified (insert/delete operations) often and you need to find the kth smallest frequently? How would you optimize the kthSmallest routine?

Show Hint 

	/**
	* Definition for a binary tree node.
	* struct TreeNode {
	* int val;
	* TreeNode *left;
	* TreeNode *right;
	* TreeNode(int x) : val(x), left(NULL), right(NULL) {}
	* };
	*/
	class Solution {
	public:
	int kthSmallest(TreeNode* root, int k) {
	stack<TreeNode*> myStack;
	TreeNode* current = root;
	int c=0;
	while(true){
	if(current){
	myStack.push(current);
	current=current->left;
	}else{
	current = myStack.top();
	myStack.pop();
	c++;
	if(c==k)
	return current->val;
	current=current->right;
	}
	}
	}
	};

view raw Q230KSmallestNodeInBST.cpp hosted with ❤ by GitHub

Round 2 solution:

	class Solution {
	public:
	void help(TreeNode* root, int& res, int k, int& i){
	if(root==NULL)
	return;
	help(root->left, res, k, i);
	if(++i==k){
	res = root->val;
	return;
	}
	help(root->right, res, k, i);
	}
	int kthSmallest(TreeNode* root, int k) {
	int res=0;
	if(root==NULL)
	return res;
	int i=0;
	help(root, res, k, i);
	return res;
	}
	};

view raw gistfile1.txt hosted with ❤ by GitHub