230. Kth Smallest Element in a BST

 一刷 05/2022

Version #1 Iteration with Stack

Runtime: 1 ms, faster than 61.45% of Java online submissions for Kth Smallest Element in a BST.

Memory Usage: 45.4 MB, less than 24.14% of Java online submissions for Kth Smallest Element in a BST.

/**

 * Definition for a binary tree node.

 * public class TreeNode {

 *     int val;

 *     TreeNode left;

 *     TreeNode right;

 *     TreeNode() {}

 *     TreeNode(int val) { this.val = val; }

 *     TreeNode(int val, TreeNode left, TreeNode right) {

 *         this.val = val;

 *         this.left = left;

 *         this.right = right;

 *     }

 * }

 */

class Solution {

    public int kthSmallest(TreeNode root, int k) {

        // Use stack to do a in order traversal of the tree

        Stack<TreeNode> stack = new Stack<>();

        pushLeft(root, stack);

        TreeNode curr = null;

        while (!stack.isEmpty() && k > 0) {

            curr = stack.pop();

            pushLeft(curr.right, stack);

            k--;

        }

        return curr.val;

    }

    

    private void pushLeft(TreeNode node, Stack<TreeNode> stack) {

        while (node != null) {

            stack.push(node);

            node = node.left;

        }

    }

}

Version #2 Recursion

Runtime: 0 ms, faster than 100.00% of Java online submissions for Kth Smallest Element in a BST.

Memory Usage: 45 MB, less than 34.62% of Java online submissions for Kth Smallest Element in a BST.

/**

 * Definition for a binary tree node.

 * public class TreeNode {

 *     int val;

 *     TreeNode left;

 *     TreeNode right;

 *     TreeNode() {}

 *     TreeNode(int val) { this.val = val; }

 *     TreeNode(int val, TreeNode left, TreeNode right) {

 *         this.val = val;

 *         this.left = left;

 *         this.right = right;

 *     }

 * }

 */

class Solution {

    public int kthSmallest(TreeNode root, int k) {

        int[] count = new int[]{k};

        int[] result = new int[]{-1};

        helper(root, count, result);

        return result[0];

    }

    

    private void helper(TreeNode node, int[] count, int[] result) {

        if (node == null) {

            return;

        }

        helper(node.left, count, result);

        if (result[0] != -1) {

            return;

        }

        if (count[0] == 1) {

            result[0] = node.val;

            return;

        }

        count[0]--;

        helper(node.right, count, result);

    }

}