230 - Kth Smallest Element in a BST
Written on November 2, 2015
Tweet
Given a binary search tree, write a function kthSmallest to find the kth smallest element in it.
public class Solution {
public int kthSmallest(TreeNode root, int k) {
if (root == null || k <= 0) return -1;
Stack<treenode> stack = new Stack<treenode>();
while (root != null || !stack.isEmpty()) {
if (root != null) {
stack.push(root);
root = root.left;
} else {
root = stack.pop();
if (k-- == 1) return root.val;
root = root.right;
}
}
return -1;
}
}
class Solution(object):
def kthSmallest(self, root, k):
"""
:type root: TreeNode
:type k: int
:rtype: int
"""
if not root:
return -1
stack = []
while stack or root:
if root:
stack.append(root)
root = root.left
else:
root = stack.pop()
k -= 1
if k == 0:
return root.val
root = root.right
return -1
