Kth Smallest Element in BST in DSA Typescript - 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 go to the left and larger numbers go to the right. You want to find the kth smallest number in this tree, which means the number that would appear in position k if you listed all numbers in order.

🎯 Goal: Build a TypeScript program that creates a BST, sets a value for k, finds the kth smallest element in the BST using an in-order traversal, and prints the result.

📋 What You'll Learn

Create a BST with the exact nodes given

Set a variable k to the given value

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

Print the kth smallest element

💡 Why This Matters

🌍 Real World

Finding the kth smallest element is useful in databases, search engines, and ranking systems where you want to quickly find a specific order statistic.

💼 Career

Understanding BSTs and order statistics is important for software engineers working on efficient data retrieval, algorithm design, and coding interviews.

1

Create the BST nodes

Create a class called TreeNode with properties 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 7,
root.left.left with value 2,
root.left.right with value 4,
root.right.left with value 6,
root.right.right with value 8.

DSA Typescript

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

Hint

Start by defining the TreeNode class with a constructor. Then create the root node and connect its left and right children as described.

2

Set the value of k

Create a variable called k and set it to 3.

DSA Typescript

class TreeNode {
    val: number;
    left: TreeNode | null;
    right: TreeNode | null;
    constructor(val: number) {
        this.val = val;
        this.left = null;
        this.right = null;
    }
}

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

// Set k to 3
// Your code here

Hint

Simply create a constant k and assign it the value 3.

3

Write the function to find kth smallest element

Write a function called kthSmallest that takes root of type TreeNode | null and k of type number. Use an in-order traversal to find and return the kth smallest element's value in the BST.

DSA Typescript

class TreeNode {
    val: number;
    left: TreeNode | null;
    right: TreeNode | null;
    constructor(val: number) {
        this.val = val;
        this.left = null;
        this.right = null;
    }
}

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

const k = 3;

// Write kthSmallest function below
// Your code here

Hint

Use a helper function inorder to visit nodes in order. Keep a count of visited nodes. When count equals k, save the node's value and stop.

4

Print the kth smallest element

Write a console.log statement to print the result of calling kthSmallest(root, k).

DSA Typescript

class TreeNode {
    val: number;
    left: TreeNode | null;
    right: TreeNode | null;
    constructor(val: number) {
        this.val = val;
        this.left = null;
        this.right = null;
    }
}

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

const k = 3;

function kthSmallest(root: TreeNode | null, k: number): number {
    let count = 0;
    let result = -1;

    function inorder(node: TreeNode | null) {
        if (!node || result !== -1) 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

Call kthSmallest(root, k) and print the result using console.log.