Kth Smallest Element in a Bst - JS Solution

Editorial

Editorial solutions and visualizations are prepared with care, but we do not guarantee 100% accuracy or completeness. Please use your own judgment to verify results. Visucodize is not responsible for decisions made based on this content.

const CURRENT = 'current', CURRENT_COLOR = 'blue';
const VISITED = 'visited', VISITED_COLOR = 'gold';
const DONE = 'done', DONE_COLOR = 'orange';
const KTH_NODE = 'kth_node', KTH_NODE_COLOR = 'green';
const IN_PROGRESS = 'in_progress', IN_PROGRESS_COLOR = 'mediumpurple';
const K_COLOR = 'gray';

function visMainFunction(treeInput, k) {
    const originalK = k;
    initClassProperties();

    const root = convertInputToTree(treeInput);

    startPartialBatch();
    const tree = new VisBinaryTree(root, { dataPropName: 'val' });
    makeVisVariable(k).options({ label: 'k (remaining rank)' }).createVis();
    explanationAndColorSchemaNotifications();
    endBatch();

    const answer = inorder(root);

    notification(`🏁 <b>Traversal complete!</b> The <b>${originalK}th smallest element</b> found is: <b>${answer}</b>.`);
    return answer;

    function inorder(node) {
        if (!node) return null;

        const vm = tree.makeVisManagerForNode(node);
        startPartialBatch();
        setCurrentNode(vm);
        notification(`
            🔵 Processing the ${makeColoredSpan('current node', CURRENT_COLOR)} —  
            as part of <b>in-order traversal</b>, we first <b>recursively visit the left subtree</b>  
            since all smaller elements in a BST lie there (if any exist).
        `);
        vm.addClass(IN_PROGRESS);
        endBatch();

        const leftResult = inorder(node.left);
        if (leftResult !== null) return leftResult;

        startPartialBatch();
        setCurrentNode(vm);
        notification(`
            🔙 Returned from the left subtree of the ${makeColoredSpan('current node', CURRENT_COLOR)}. Now visiting the ${makeColoredSpan('current node', CURRENT_COLOR)} itself.
            <br>📉 Decrementing ${makeColoredSpan('k', K_COLOR)} — representing how many more nodes we need to visit before reaching the ${originalK}th smallest element.
        `);
        k -= 1;

        if (k === 0) {
            notification(`
                🎯 ${makeColoredSpan('k', K_COLOR)} has reached <b>0</b> —  
                meaning the ${makeColoredSpan('current node', CURRENT_COLOR)} is <b>the ${originalK}th smallest element!</b>  
                Highlighting it with a ${makeColoredSpan('green background', KTH_NODE_COLOR)}.
            `);
            vm.removeClass(IN_PROGRESS).addClass(KTH_NODE);
            endBatch();
            return node.val;
        }

        vm.removeClass(IN_PROGRESS).addClass(VISITED);
        notification(`
            ✅ Finished visiting the ${makeColoredSpan('current node', CURRENT_COLOR)}.  
            As part of <b>in-order traversal</b>, now <b>recursively visiting the right subtree</b> to discover the next elements in order.
        `);
        endBatch();

        const result = inorder(node.right);
        startPartialBatch();
        setCurrentNode(vm);
        notification(`
            🔙 Finished processing the <b>right subtree</b> of the ${makeColoredSpan('current node', CURRENT_COLOR)} —  
            this completes the <b>in-order traversal</b> for this node’s entire subtree.
        `);
        vm.removeClass(VISITED).addClass(DONE);
        endBatch();
        return result;
    }
}

// --- Visual helpers ---

let currentNodeVM = null;

function setCurrentNode(vm) {
    if (currentNodeVM) currentNodeVM.removeClass(CURRENT);
    vm.addClass(CURRENT);
    currentNodeVM = vm; 
}

function initClassProperties() {
    setClassProperties(CURRENT, { borderColor: CURRENT_COLOR });
    setClassProperties(VISITED, { backgroundColor: VISITED_COLOR });
    setClassProperties(DONE, { backgroundColor: DONE_COLOR });
    setClassProperties(KTH_NODE, { backgroundColor: KTH_NODE_COLOR });
    setClassProperties(IN_PROGRESS, { backgroundColor: IN_PROGRESS_COLOR });
}

function convertInputToTree(arr) {
    if (!arr.length || arr[0] === null) return null;
    const nodes = arr.map(val => (val === null ? null : new TreeNode(val)));
    for (let i = 0; i < arr.length; i++) {
        if (nodes[i]) {
            nodes[i].left = nodes[2 * i + 1] || null;
            nodes[i].right = nodes[2 * i + 2] || null;
        }
    }
    return nodes[0];
}

function TreeNode(val, left = null, right = null) {
    this.val = val;
    this.left = left;
    this.right = right;
}

function explanationAndColorSchemaNotifications() {
  explanationNotification();

  notification(`
    <b>🎨 Visual Cues (Color Schema)</b>
    <ul>
      <li>${makeColoredSpan('Current node', CURRENT_COLOR)} — <b>${CURRENT_COLOR} border</b> while focused/being processed.</li>
      <li>${makeColoredSpan('In-progress node', IN_PROGRESS_COLOR)} — <b>${IN_PROGRESS_COLOR} background</b> while exploring its left subtree (not yet visited).</li>
      <li>${makeColoredSpan('Visited node', VISITED_COLOR)} — <b>${VISITED_COLOR} background</b> after the node is visited (counted) and before finishing its right subtree.</li>
      <li>${makeColoredSpan('Done node', DONE_COLOR)} — <b>${DONE_COLOR} background</b> once the node’s right subtree is fully processed.</li>
      <li>${makeColoredSpan('kth smallest', KTH_NODE_COLOR)} — <b>${KTH_NODE_COLOR} background</b> when <code>k</code> reaches 0 at this node.</li>
    </ul>
  `);
}

Approach

We leverage the fact that an in-order traversal of a Binary Search Tree (BST) visits nodes in ascending order. The provided k parameter acts as a mutable downward counter indicating how many more nodes remain before we reach the kth smallest element. Each time we “visit” a node (i.e., process it between its left and right recursive calls), we decrement k. When k reaches 0 immediately after visiting a node, that node is the kth smallest. If a non-null result is returned from the left subtree, it means the kth smallest element was found there, so we return it immediately, allowing the result value to naturally propagate upward through the recursion stack after it is found.

🔧 Traversal Logic

Base case: If the current node is null, return null — signaling that no result was found in this branch.
Go left first: Recursively traverse the left subtree to enumerate all smaller values (if any).
Bubble up early if found on the left: If the left recursion returns a non-null value, it means the kth smallest element was already found there, so we return it immediately — skipping the current node and its right subtree.
Visit node: Otherwise, process the current node and decrement k.
Result-found condition: When k == 0 after visiting a node, we’ve found the kth smallest element. Return it immediately — the result propagates up the recursion stack.
Then go right: If the kth element wasn’t found in the left subtree or the current node, we recurse into the right subtree to continue counting larger elements in ascending order. The recursive call will inevitably return the correct result, so we can unconditionally return its value upward.

🧠 Correctness Intuition

In a BST, left-subtree values are smaller and right-subtree values are larger. Thus, in-order traversal yields a strictly increasing sequence. Counting down k at each visit aligns with the node’s rank in that order — when k hits 0, we’re at the kth smallest. Early return after the left recursion (when it already found the answer) preserves correctness and avoids unnecessary work.

🧭 Result Semantics

When k reaches 0 upon visiting a node, that node’s value is the kth smallest. The function returns it immediately, and the value is bubbled up through recursive returns to the caller.

Time Complexity

Let h be the tree height and n be the tree size.
O(h + k) — at most h recursive calls are active at a time, and k nodes are visited to decrement the counter before finding the result. Worst case O(n) when k = n or the tree is skewed going down left.

Space Complexity

Let h be the tree height and n be the tree size.
O(h) — the recursion stack depth is upper-bounded by the tree’s height (O(log n) for balanced trees, O(n) for skewed ones).

Input-1

Kth Smallest Element in a Bst - JS Solution

Solution code

Solution explanation

Solution explanation

Approach

🔧 Traversal Logic

🧠 Correctness Intuition

🧭 Result Semantics

Time Complexity

Space Complexity