Find Kth node in BST
https://leetcode.com/problems/kth-smallest-element-in-a-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?
Solution 1: Inorder traversal
public class Solution {
public int kthSmallest(TreeNode root, int k) {
if (root == null || k <= 0) {
return -1;
}
Stack<TreeNode> stack = new Stack();
while (!stack.isEmpty() || root != null) {
if (root != null) {
stack.push(root);
root = root.left;
}
else {
root = stack.pop();
k--;
if (k == 0) {
return root.val;
}
root = root.right;
}
}
return -1;
}
}
Followup: data structure
ref: http://www.geeksforgeeks.org/find-k-th-smallest-element-in-bst-order-statistics-in-bst/
idea:
The idea is to maintain rank of each node. We can keep track of elements in a subtree of any node while building the tree. Since we need K-th smallest element, we can maintain number of elements of left subtree in every node.
Assume that the root is having N nodes in its left subtree. If K = N + 1, root is K-th node. If K < N, we will continue our search (recursion) for the Kth smallest element in the left subtree of root. If K > N + 1, we continue our search in the right subtree for the (K – N – 1)-th smallest element. Note that we need the count of elements in left subtree only.
Time complexity: O(h) where h is height of tree.
Algorithm:
start:
if K = root.leftElement + 1
root node is the K th node.
goto stop
else if K > root.leftElements
K = K - (root.leftElements + 1)
root = root.right
goto start
else
root = root.left
goto srart
stop: