BST Property and Why It Matters in DSA Typescript - Build from Scratch

BST Property and Why It Matters

📖 Scenario: Imagine you are organizing a collection of books by their unique ID numbers. You want to store them so that you can quickly find any book by its ID. A Binary Search Tree (BST) helps you do this by keeping smaller IDs on the left and larger IDs on the right.

🎯 Goal: You will build a simple Binary Search Tree (BST) with three nodes and then print the tree structure to see how the BST property keeps the data organized.

📋 What You'll Learn

Create a BST node class with value, left, and right properties

Create three nodes with values 10, 5, and 15

Link the nodes to form a BST where 5 is left child of 10 and 15 is right child of 10

Print the tree nodes in order: root, left child, right child

💡 Why This Matters

🌍 Real World

BSTs are used in databases and file systems to quickly find, add, or remove data by keeping it organized.

💼 Career

Understanding BSTs helps in software engineering roles that involve data storage, search optimization, and algorithm design.

1

Create BST Node Class

Create a class called BSTNode with a constructor that takes a value of type number and initializes left and right properties to null.

DSA Typescript

// Your code here

Hint

Think of each node as a box holding a number and two empty spots for smaller and larger numbers.

2

Create Three BST Nodes

Create three variables called root, leftChild, and rightChild and assign them new BSTNode instances with values 10, 5, and 15 respectively.

DSA Typescript

class BSTNode {
    value: number;
    left: BSTNode | null;
    right: BSTNode | null;

    constructor(value: number) {
        this.value = value;
        this.left = null;
        this.right = null;
    }
}

// Create three BSTNode instances
// Your code here

Hint

Use the new keyword to create nodes with the given values.

3

Link Nodes to Form BST

Link the nodes by setting root.left to leftChild and root.right to rightChild to form a BST where smaller values go left and larger values go right.

DSA Typescript

class BSTNode {
    value: number;
    left: BSTNode | null;
    right: BSTNode | null;

    constructor(value: number) {
        this.value = value;
        this.left = null;
        this.right = null;
    }
}

const root = new BSTNode(10);
const leftChild = new BSTNode(5);
const rightChild = new BSTNode(15);

// Link nodes to form BST
// Your code here

Hint

Remember, smaller values go to the left child, larger values to the right child.

4

Print BST Node Values

Print the values of root, root.left, and root.right in order using three separate console.log statements.

DSA Typescript

class BSTNode {
    value: number;
    left: BSTNode | null;
    right: BSTNode | null;

    constructor(value: number) {
        this.value = value;
        this.left = null;
        this.right = null;
    }
}

const root = new BSTNode(10);
const leftChild = new BSTNode(5);
const rightChild = new BSTNode(15);

root.left = leftChild;
root.right = rightChild;

// Print the values of root, root.left, and root.right
// Your code here

Hint

Use console.log to print each node's value. Use optional chaining ?. for safety.

Practice

1. What is the main property that defines a Binary Search Tree (BST)?

easy

A. Left child nodes have smaller values, right child nodes have larger values

B. All nodes have exactly two children

C. Nodes are arranged in a circular linked list

D. Each node stores the sum of its children

Solution

1. Step 1: Understand BST node arrangement

   In a BST, every node's left child has a smaller value and the right child has a larger value.

2. Step 2: Compare with other options

   Other options describe different data structures or incorrect properties.

3. Final Answer:

   Left child nodes have smaller values, right child nodes have larger values -> Option A

4. Quick Check:

   BST property = Left smaller, right larger [OK]

Hint: Remember BST orders left < node < right [OK]

Common Mistakes:

• Thinking all nodes must have two children
• Confusing BST with binary tree
• Assuming nodes store sums

2. Which TypeScript interface correctly represents a BST node?

easy

A. interface Node { value: number; parent: Node; }

B. interface Node { value: number; left: Node | null; right: Node | null; }

C. interface Node { value: number; children: Node[]; }

D. interface Node { value: number; next: Node | null; prev: Node | null; }

Solution

1. Step 1: Identify BST node structure

   A BST node has a value and two pointers: left and right, which can be null.

2. Step 2: Check options

   interface Node { value: number; left: Node | null; right: Node | null; } matches this structure; others describe linked lists or generic trees.

3. Final Answer:

   interface Node { value: number; left: Node | null; right: Node | null; } -> Option B

4. Quick Check:

   BST node = value + left + right [OK]

Hint: BST nodes have left and right, not next/prev [OK]

Common Mistakes:

• Using next/prev like linked lists
• Using children array for BST
• Missing null for leaf nodes

3. What will be the in-order traversal output of this BST?

const root = {
  value: 10,
  left: { value: 5, left: null, right: null },
  right: { value: 15, left: null, right: null }
};
function inorder(node) {
  if (!node) return [];
  return [...inorder(node.left), node.value, ...inorder(node.right)];
}
console.log(inorder(root));

medium

A. [10, 5, 15]

B. [5, 15, 10]

C. [15, 10, 5]

D. [5, 10, 15]

Solution

1. Step 1: Understand in-order traversal

   In-order visits left subtree, then node, then right subtree.

2. Step 2: Apply traversal to given tree

   Left subtree: 5, root: 10, right subtree: 15, so output is [5, 10, 15].

3. Final Answer:

   [5, 10, 15] -> Option D

4. Quick Check:

   In-order = left, root, right = [5,10,15] [OK]

Hint: In-order traversal of BST gives sorted values [OK]

Common Mistakes:

• Confusing pre-order or post-order with in-order
• Mixing left and right subtree order
• Forgetting to return empty array for null

4. Identify the bug in this BST insertion function:

function insert(node, value) {
  if (!node) return { value, left: null, right: null };
  if (value < node.value) insert(node.left, value);
  else insert(node.right, value);
  return node;
}

medium

A. Node should have a parent pointer

B. Should compare value > node.value instead of <

C. Missing return when recursively inserting left or right

D. Function should not return anything

Solution

1. Step 1: Analyze recursive calls

   The recursive calls to insert do not assign their results back to node.left or node.right.

2. Step 2: Fix missing assignment

   We must assign: node.left = insert(node.left, value) or node.right = insert(node.right, value) to update the tree.

3. Final Answer:

   Missing return when recursively inserting left or right -> Option C

4. Quick Check:

   Recursive insert must update child pointers [OK]

Hint: Always assign recursive insert result to child pointer [OK]

Common Mistakes:

• Not assigning recursive call result
• Wrong comparison operator
• Expecting parent pointer in BST node

5. Given a BST, why is maintaining the BST property important when deleting a node?

hard

A. To ensure in-order traversal still returns sorted values

B. To keep the tree balanced automatically

C. To allow duplicate values in the tree

D. To convert the BST into a linked list

Solution

1. Step 1: Understand BST property role

   The BST property ensures left < node < right, which makes in-order traversal sorted.

2. Step 2: Effect of deletion on BST property

   If deletion breaks this property, in-order traversal won't be sorted, breaking BST usefulness.

3. Final Answer:

   To ensure in-order traversal still returns sorted values -> Option A

4. Quick Check:

   BST property keeps in-order sorted [OK]

Hint: BST property keeps traversal sorted after deletion [OK]

Common Mistakes:

• Thinking BST auto-balances on deletion
• Assuming duplicates are allowed by default
• Confusing BST with linked list