My short O(k) java solution, using a stack


  • 0
    H
    private Stack<TreeNode> stack = new Stack<TreeNode>();
    
    public int kthSmallest(TreeNode root, int k) {
        findLeft(root);
        for (int i = 0; i < k - 1; i++) findLeft(stack.pop().right);
        return stack.pop().val;
    }
    
    private void findLeft(TreeNode root) {
        while (root != null) {
            stack.push(root);
            root = root.left;
        }
    }

Log in to reply
 

Looks like your connection to LeetCode Discuss was lost, please wait while we try to reconnect.