Given a binary search tree, write a function to find the kth smallest element in the tree.
Example :
Input :
2
/ \
1 3
and k = 2
Return : 2
As 2 is the second smallest element in the tree.
NOTE : You may assume 1 <= k <= Total number of nodes in BST
Method:
In order iterator
Solution:
Time: O(k) Space: O(k)
/** * Definition for binary tree * class TreeNode { * int val; * TreeNode left; * TreeNode right; * TreeNode(int x) { * val = x; * left=null; * right=null; * } * } */ public class Solution { public int kthsmallest(TreeNode A, int B) { Deque<TreeNode> stack = new ArrayDeque<>(); TreeNode curr = A; int i = 0; while (curr != null || !stack.isEmpty()) { while (curr != null) { stack.push(curr); curr = curr.left; } if (!stack.isEmpty()) { curr = stack.pop(); i ++; if (i == B) { return curr.val; } curr = curr.right; } } return -1; } }