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.

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?

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?

Hint:

- Try to utilize the property of a BST.
- What if you could modify the BST node's structure?
- The optimal runtime complexity is O(height of BST).

**Code (Java):**

/** * Definition for a binary tree node. * public class TreeNode { * int val; * TreeNode left; * TreeNode right; * TreeNode(int x) { val = x; } * } */ public class Solution { private int counter = 0; private boolean found = false; private int val = Integer.MIN_VALUE; public int kthSmallest(TreeNode root, int k) { if (root == null) { return 0; } kthSmallestHelper(root, k); return val; } private void kthSmallestHelper(TreeNode root, int k) { if (root == null) { return; } if (!found) { kthSmallestHelper(root.left, k); } counter++; if (counter == k) { found = true; val = root.val; } if (!found) { kthSmallestHelper(root.right, k); } } }

**An O(h) solution:**

If the BST node's structure can be modified. We let each node maintain the number of nodes of its left subtree. Therefore, for each node, we can compare k with the number of its subtree.

**Code (Java):**

/** * Definition for a binary tree node. * public class TreeNode { * int val; * TreeNode left; * TreeNode right; * TreeNode(int x) { val = x; } * } */ public class Solution { public int kthSmallest(TreeNode root, int k) { if (root == null) { return 0; } int leftNodes = getNumberNodes(root.left); if(k == leftNodes + 1) { return root.val; } else if (k > leftNodes + 1) { return kthSmallest(root.right, k - leftNodes - 1); } else { return kthSmallest(root.left, k); } } private int getNumberNodes(TreeNode root) { if (root == null) { return 0; } return getNumberNodes(root.left) + getNumberNodes(root.right) + 1; } }

## No comments:

## Post a Comment