Kth Smallest Element in BST in DSA Javascript - Build from Scratch

Kth Smallest Element in BST

📖 Scenario: You are working with a Binary Search Tree (BST) that stores numbers in a way that smaller numbers are on the left and larger numbers are on the right. You want to find the kth smallest number in this tree, which means the number that would appear in position k if all numbers were sorted from smallest to largest.

🎯 Goal: Build a program that finds the kth smallest element in a given BST using an in-order traversal technique.

📋 What You'll Learn

Create a BST with the exact nodes given

Set a variable k to the exact value given

Write a function kthSmallest that finds the kth smallest element using in-order traversal

Print the kth smallest element exactly as shown

💡 Why This Matters

🌍 Real World

Finding the kth smallest element is useful in databases and search engines where you want to quickly find ranked data without sorting everything.

💼 Career

Understanding tree traversal and selection algorithms is important for software engineers working on data processing, optimization, and system design.

1

Create the BST nodes

Create a class called TreeNode with a constructor that takes val, left, and right. Then create the BST with these exact nodes and connections:
root with value 5,
root.left with value 3,
root.right with value 6,
root.left.left with value 2,
root.left.right with value 4,
root.left.left.left with value 1.

DSA Javascript

// Define TreeNode class and create the BST nodes as described
// Your code here

Hint

Remember to create the TreeNode class first, then build the tree by linking nodes as left and right children.

2

Set the value of k

Create a variable called k and set it to 3.

DSA Javascript

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

const root = new TreeNode(5);
root.left = new TreeNode(3);
root.right = new TreeNode(6);
root.left.left = new TreeNode(2);
root.left.right = new TreeNode(4);
root.left.left.left = new TreeNode(1);

// Set k to 3
// Your code here

Hint

Just create a constant named k and assign it the value 3.

3

Write the kthSmallest function

Write a function called kthSmallest that takes root and k as parameters. Use an in-order traversal to find the kth smallest element. Use a helper function inside to traverse the tree and keep track of the count. Return the kth smallest value.

DSA Javascript

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

const root = new TreeNode(5);
root.left = new TreeNode(3);
root.right = new TreeNode(6);
root.left.left = new TreeNode(2);
root.left.right = new TreeNode(4);
root.left.left.left = new TreeNode(1);

const k = 3;

// Write kthSmallest function here
// Your code here

Hint

Use a helper function inorder to visit nodes in order. Increase a count each time you visit a node. When count equals k, save the node's value and stop.

4

Print the kth smallest element

Print the result of calling kthSmallest(root, k).

DSA Javascript

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

const root = new TreeNode(5);
root.left = new TreeNode(3);
root.right = new TreeNode(6);
root.left.left = new TreeNode(2);
root.left.right = new TreeNode(4);
root.left.left.left = new TreeNode(1);

const k = 3;

function kthSmallest(root, k) {
    let count = 0;
    let result = null;

    function inorder(node) {
        if (!node || result !== null) return;
        inorder(node.left);
        count++;
        if (count === k) {
            result = node.val;
            return;
        }
        inorder(node.right);
    }

    inorder(root);
    return result;
}

// Print the kth smallest element
// Your code here

Hint

Use console.log to print the result of kthSmallest(root, k).