Difficulty: Medium · LeetCode 230

Problem

Given root of BST and integer k, return k-th smallest value (1-indexed) in tree.

Understanding the problem

An in-order traversal of a BST visits nodes in strictly ascending sorted order.

Intuition

Iterative stack inorder traversal stopping immediately when kth node is reached.

Approach

Use explicit stack for inorder traversal.
Push left children until node is None.
Pop node, decrement k. If k == 0 return node.val.
Set node = node.right and continue.

Naive Solution

Store the complete inorder traversal in a list and return values[k-1].

Python

class Solution:
    def kthSmallest(self, root, k):
        values = []

        def inorder(node):
            if not node:
                return

            inorder(node.left)
            values.append(node.val)
            inorder(node.right)

        inorder(root)

        return values[k - 1]

C++

class Solution {
public:
    int kthSmallest(TreeNode* root, int k) {
        vector<int> values;
        inorder(root, values);

        return values[k - 1];
    }

private:
    void inorder(TreeNode* node, vector<int>& values) {
        if (!node) return;

        inorder(node->left, values);
        values.push_back(node->val);
        inorder(node->right, values);
    }
};

Java

class Solution {
    public int kthSmallest(TreeNode root, int k) {
        List<Integer> values = new ArrayList<>();
        inorder(root, values);

        return values.get(k - 1);
    }

    private void inorder(TreeNode node, List<Integer> values) {
        if (node == null) return;

        inorder(node.left, values);
        values.add(node.val);
        inorder(node.right, values);
    }
}

JavaScript

var kthSmallest = function(root, k) {
    const values = [];

    const inorder = (node) => {
        if (!node) return;

        inorder(node.left);
        values.push(node.val);
        inorder(node.right);
    };

    inorder(root);

    return values[k - 1];
};

Time: O(n) · Aux Space: O(n)

Optimized Code (Python 3)

Python

class Solution:
    def kthSmallest(self, root, k):
        stack = []
        node = root

        while True:
            while node:
                stack.append(node)
                node = node.left

            node = stack.pop()
            k -= 1

            if k == 0:
                return node.val

            node = node.right

C++

class Solution {
public:
    int kthSmallest(TreeNode* root, int k) {
        stack<TreeNode*> st;
        TreeNode* node = root;

        while (true) {
            while (node) {
                st.push(node);
                node = node->left;
            }

            node = st.top();
            st.pop();
            k--;

            if (k == 0) return node->val;

            node = node->right;
        }
    }
};

Java

class Solution {
    public int kthSmallest(TreeNode root, int k) {
        Deque<TreeNode> stack = new ArrayDeque<>();
        TreeNode node = root;

        while (true) {
            while (node != null) {
                stack.push(node);
                node = node.left;
            }

            node = stack.pop();
            k--;

            if (k == 0) return node.val;

            node = node.right;
        }
    }
}

JavaScript

var kthSmallest = function(root, k) {
    const stack = [];
    let node = root;

    while (true) {
        while (node) {
            stack.push(node);
            node = node.left;
        }

        node = stack.pop();
        k--;

        if (k === 0) return node.val;

        node = node.right;
    }
};

Time: O(h + k) · Aux Space: O(h)

Takeaway

Pattern: BST + inorder = sorted order.