230. Kth Smallest Element in a BST (Medium)

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.

Example 1:

Input: root = [3,1,4,null,2], k = 1
   3
  / \
 1   4
  \
   2
Output: 1

Example 2:

Input: root = [5,3,6,2,4,null,null,1], k = 3
       5
      / \
     3   6
    / \
   2   4
  /
 1
Output: 3

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?

Solutions

1.

class Solution {

    // Traverse the binary search tree by non-recursive way.

    public int kthSmallest(TreeNode root, int k) {
        Stack<TreeNode> stack = new Stack<>();

        TreeNode p = root;
        stack.push(p);

        // using loop instead of recursion
        while (!stack.isEmpty() || p != null) {
            // visit left until no child
            if (p != null) {
                stack.push(p);
                p = p.left;
                continue;
            }

            // p = null && stack not empty

            // visit stack top
            TreeNode t = stack.pop();
            k--;
            if (k == 0) {
                return t.val;
            }

            p = t.right; // visit right
        }

        // never reached
        return -1;
    }
}

2.

class Solution {

    // Traverse the binary search tree by recursive way.

    public int kthSmallest(TreeNode root, int k) {
        Stack<Integer> track = new Stack<>();

        recurse(root, k, track);

        return track.pop();
    }

    public int recurse(TreeNode root, int k, Stack<Integer> track) {

        // This should be placed at the head of function since priority of return 1
        // weighs much more than return 0. return 1 means all the recursion
        // searching should ceased immediately.

        if (track.size() == k) {
            // already find the target value, break down searching task
            return 1;
        }

        if (root == null) {
            return 0;
        }

        int rst = recurse(root.left, k, track);
        if (rst == 1) { // break down searching
            return rst;
        }

        track.push(root.val);

        rst = recurse(root.right, k, track);

        return rst;
    }
}

Incorrect Solutions

References

https://www.programcreek.com/2014/07/leetcode-kth-smallest-element-in-a-bst-java/

Copyright © iovi.com 2017 all right reserved,powered by GitbookLast Modification: 2020-03-21 16:29:23

results matching ""

    No results matching ""