{"title":"Introduction to BST","description":null,"content":"**Binary Search Tree (BST)** is a data structure that combines the hierarchical structure of binary tree with the ordering of a sorted list, and the efficiency of binary search.\n\nThis structure makes **searching, inserting, and deleting elements** efficient, often in **O(log n)** time when the tree is balanced.\n\nBSTs (and their self-balancing variants like AVL and red-black trees) back the ordered map and set types in many standard libraries: Java's `TreeMap`, C++'s `std::map`, and similar structures elsewhere. They show up wherever we need fast lookups while maintaining sorted order. They are also an important topic for coding interviews, especially in problems that involve dynamic insertions, deletions, and ordered traversal.\n\nIn this chapter, I'll cover:\n\n- What a BST is and how it works\n- The core operations: **search, insert, and delete**\n- Different types of BSTs\n- How to implement a BST in code\n\n---\n\n# What is a Binary Search Tree?\n\nA **Binary Search Tree** is a binary tree with one extra rule, the **BST property**:\n\nFor every node:\n\n- All values in the **left subtree** are **smaller** than the node's value.\n- All values in the **right subtree** are **greater** than the node's value.\n\nThis property is what enables logarithmic operations: at each step, the search space halves, similar to how **binary search** works on a sorted array.\n\nConsider inserting the values `50, 30, 70, 20, 40, 60, 80` into an empty tree. A balanced BST looks like this:\n\n\n\n\n- The left subtree of `50` contains values smaller than 50: {20, 30, 40}.\n- The right subtree of `50` contains values greater than 50: {60, 70, 80}.\n- The same property holds at every node in the tree.\n\nTo search for `60`:\n\n- Start at `50`; since 60 is greater, move right.\n- At `70`; since 60 is smaller, move left.\n- Found `60`.\n\nEach comparison eliminates half of the remaining nodes, instead of scanning every node like in a linked list.\n\n- A **balanced BST** keeps its height close to log(n), so operations are typically O(log n)\n- Examples of balanced BSTs include AVL Trees, and Red-Black Trees.\n- An **unbalanced BST** can degrade to a linked list if nodes are inserted in sorted order making operations **O(n) in the worst case**\n\n---\n\n# Key Operations in BSTs\n\nBSTs support four core operations: **search, insert, delete, and traversal**. The examples below use this balanced BST:\n\n\n\n\nAll code examples will be methods within this basic BST class structure:\n\n\n```java\nclass BST {\n \n // Defines the structure of a single node\n class Node {\n int val;\n Node left, right;\n\n public Node(int val) {\n this.val = val;\n this.left = null;\n this.right = null;\n }\n }\n\n Node root; // The entry point to our tree\n\n // ... operations will go here ...\n}\n```\n\n```python\nclass BST:\n # Defines the structure of a single node\n class Node:\n def __init__(self, val: int):\n self.val = val\n self.left = None\n self.right = None\n \n def __init__(self):\n self.root = None # The entry point to our tree\n # ... operations will go here ...\n```\n\n```cpp\nclass BST {\nprivate:\n // Defines the structure of a single node\n class Node {\n public:\n int val;\n Node* left;\n Node* right;\n \n Node(int val) {\n this->val = val;\n this->left = nullptr;\n this->right = nullptr;\n }\n };\n \n Node* root; // The entry point to our tree\n \npublic:\n BST() {\n root = nullptr;\n }\n \n // ... operations will go here ...\n};\n```\n\n```csharp\npublic class BST {\n // Defines the structure of a single node\n private class Node {\n public int val;\n public Node left;\n public Node right;\n \n public Node(int val) {\n this.val = val;\n this.left = null;\n this.right = null;\n }\n }\n \n private Node root; // The entry point to our tree\n \n public BST() {\n root = null;\n }\n \n // ... operations will go here ...\n}\n```\n\n```go\ntype BST struct {\n root *Node\n}\n\n// Defines the structure of a single node\ntype Node struct {\n val int\n left *Node\n right *Node\n}\n\nfunc NewNode(val int) *Node {\n return &Node{\n val: val,\n left: nil,\n right: nil,\n }\n}\n\nfunc NewBST() *BST {\n return &BST{\n root: nil, // The entry point to our tree\n }\n}\n\n// ... operations will go here ...\n```\n\n```rust\npub struct BST {\n root: Option>, // The entry point to our tree\n}\n\nimpl BST {\n pub fn new() -> Self {\n BST { root: None }\n }\n\n // ... operations will go here ...\n}\n\n// Defines the structure of a single node\nstruct Node {\n val: i32,\n left: Option>,\n right: Option>,\n}\n\nimpl Node {\n fn new(val: i32) -> Self {\n Node {\n val,\n left: None,\n right: None,\n }\n }\n}\n```\n\n```javascript\nclass BST {\n constructor() {\n this.root = null; // The entry point to our tree\n // ... operations will go here ...\n }\n}\n\n// Defines the structure of a single node\nclass Node {\n constructor(val) {\n this.val = val;\n this.left = null;\n this.right = null;\n }\n}\n```\n\n```typescript\nclass BST {\n // Defines the structure of a single node\n private class Node {\n val: number;\n left: Node | null;\n right: Node | null;\n \n constructor(val: number) {\n this.val = val;\n this.left = null;\n this.right = null;\n }\n }\n \n private root: Node | null; // The entry point to our tree\n \n constructor() {\n this.root = null;\n // ... operations will go here ...\n }\n}\n```\n\n\n### 1. Search\n\nSearching in a BST works like binary search on a sorted array.\n\n**Here's the algorithm:**\n\n1. **Base Case 1 (Not Found):** If the current `root` is `null`, we've hit a dead end. The `target` is not in the tree, so return `false`.\n2. **Base Case 2 (Found):** If the current `root.val` is equal to the `target`, we've found it! Return `true`.\n3. **Recursive Step (Go Left):** If the `target` is less than the `root.val`, it *must* be in the left subtree. Return the result of calling `search` on the `root.left`.\n4. **Recursive Step (Go Right):** Otherwise (if `target` is greater than `root.val`), it *must* be in the right subtree. Return the result of calling `search` on the `root.right`.\n\n\n```java\npublic boolean search(Node root, int target) {\n // Base Case 1: We've hit a dead end\n if (root == null) {\n return false;\n }\n \n // Base Case 2: We've found the value\n if (root.val == target) {\n return true;\n }\n \n // Recursive Step: Decide where to go next\n if (target < root.val) {\n return search(root.left, target);\n } else {\n return search(root.right, target);\n }\n}\n```\n\n```python\ndef search(self, root: Node, target: int) -> bool:\n # Base Case 1: We've hit a dead end\n if root is None:\n return False\n \n # Base Case 2: We've found the value\n if root.val == target:\n return True\n \n # Recursive Step: Decide where to go next\n if target < root.val:\n return self.search(root.left, target)\n else:\n return self.search(root.right, target)\n```\n\n```cpp\nbool search(Node* root, int target) {\n // Base Case 1: We've hit a dead end\n if (root == nullptr) {\n return false;\n }\n \n // Base Case 2: We've found the value\n if (root->val == target) {\n return true;\n }\n \n // Recursive Step: Decide where to go next\n if (target < root->val) {\n return search(root->left, target);\n } else {\n return search(root->right, target);\n }\n}\n```\n\n```csharp\npublic bool Search(Node root, int target) {\n // Base Case 1: We've hit a dead end\n if (root == null) {\n return false;\n }\n \n // Base Case 2: We've found the value\n if (root.val == target) {\n return true;\n }\n \n // Recursive Step: Decide where to go next\n if (target < root.val) {\n return Search(root.left, target);\n } else {\n return Search(root.right, target);\n }\n}\n```\n\n```go\nfunc (b *BST) search(root *Node, target int) bool {\n // Base Case 1: We've hit a dead end\n if root == nil {\n return false\n }\n \n // Base Case 2: We've found the value\n if root.val == target {\n return true\n }\n \n // Recursive Step: Decide where to go next\n if target < root.val {\n return b.search(root.left, target)\n } else {\n return b.search(root.right, target)\n }\n}\n```\n\n```rust\npub struct Solution;\n\nimpl Solution {\n pub fn search(root: Option>, target: i32) -> bool {\n // Base Case 1: We've hit a dead end\n if root.is_none() {\n return false;\n }\n\n let node = root.unwrap();\n\n // Base Case 2: We've found the value\n if node.val == target {\n return true;\n }\n\n // Recursive Step: Decide where to go next\n if target < node.val {\n Solution::search(node.left, target)\n } else {\n Solution::search(node.right, target)\n }\n }\n}\n```\n\n```javascript\nsearch(root, target) {\n // Base Case 1: We've hit a dead end\n if (root === null) {\n return false;\n }\n \n // Base Case 2: We've found the value\n if (root.val === target) {\n return true;\n }\n \n // Recursive Step: Decide where to go next\n if (target < root.val) {\n return this.search(root.left, target);\n } else {\n return this.search(root.right, target);\n }\n}\n```\n\n```typescript\nprivate search(root: Node | null, target: number): boolean {\n // Base Case 1: We've hit a dead end\n if (root === null) {\n return false;\n }\n \n // Base Case 2: We've found the value\n if (root.val === target) {\n return true;\n }\n \n // Recursive Step: Decide where to go next\n if (target < root.val) {\n return this.search(root.left, target);\n } else {\n return this.search(root.right, target);\n }\n}\n```\n\n\n**Example:** Let's say you are searching for `60`:\n\n- Start at 50. Since 60 is larger → go right.\n- At 70, since 60 is smaller → go left.\n- Found 60. Search is complete.\n\nAverage time complexity for search is **O(log n)** when the tree is balanced since each comparison eliminates roughly half of the remaining nodes.\n\nBut in the worst case it is O(n), if the tree is unbalanced (or skewed). For example, if you insert numbers in sorted order (1, 2, 3, 4, 5), it degenerates into a linked list.\n\nSearching for `5` would require visiting every single node.\n\n### 2. Insertion\n\nInsertion works almost the same way as search.\n\nWe \"search\" for the value, and when we hit a `null` spot, we know that's where the new node belongs.\n\nHere's what it looks like in code:\n\n1. If the current node (`root`) is `null`, we've found the empty spot. Create a new `Node(val)` and return it. This returned node will be assigned as the child of the parent node (from the *previous* recursive call).\n2. If `val < root.val`, recursively call `insert` on the **left subtree**. Set the current node's `left` child to be the result of this recursive call (this handles the linking).\n3. If `val > root.val`, recursively call `insert` on the **right subtree**. Set the current node's `right` child to be the result of this recursive call.\n4. Otherwise, the value already exists, so we return the current `root` unchanged. This passes the node's reference back up the call stack, keeping all links intact.\n\n\n```java\n/**\n * Inserts a new value into the BST.\n * Returns the root of the (potentially modified) subtree.\n */\npublic Node insert(Node root, int val) {\n // Base Case: We found the empty spot. Create the new\n // node and return it to be linked by its parent.\n if (root == null) {\n return new Node(val);\n }\n\n // Recursive Step: Go left or right\n if (val < root.val) {\n // Set the left child to be the result of inserting\n // into the left subtree\n root.left = insert(root.left, val);\n } else if (val > root.val) {\n // Set the right child to be the result of inserting\n // into the right subtree\n root.right = insert(root.right, val);\n }\n // else (val == root.val): value already exists, do nothing.\n\n // Return the (unchanged) root node pointer\n return root;\n}\n```\n\n```python\ndef insert(self, root: Node, val: int) -> Node:\n \"\"\"\n Inserts a new value into the BST.\n Returns the root of the (potentially modified) subtree.\n \"\"\"\n # Base Case: We found the empty spot. Create the new\n # node and return it to be linked by its parent.\n if root is None:\n return self.Node(val)\n \n # Recursive Step: Go left or right\n if val < root.val:\n # Set the left child to be the result of inserting\n # into the left subtree\n root.left = self.insert(root.left, val)\n elif val > root.val:\n # Set the right child to be the result of inserting\n # into the right subtree\n root.right = self.insert(root.right, val)\n # else (val == root.val): value already exists, do nothing.\n \n # Return the (unchanged) root node pointer\n return root\n```\n\n```cpp\n/**\n * Inserts a new value into the BST.\n * Returns the root of the (potentially modified) subtree.\n */\nNode* insert(Node* root, int val) {\n // Base Case: We found the empty spot. Create the new\n // node and return it to be linked by its parent.\n if (root == nullptr) {\n return new Node(val);\n }\n \n // Recursive Step: Go left or right\n if (val < root->val) {\n // Set the left child to be the result of inserting\n // into the left subtree\n root->left = insert(root->left, val);\n } else if (val > root->val) {\n // Set the right child to be the result of inserting\n // into the right subtree\n root->right = insert(root->right, val);\n }\n // else (val == root->val): value already exists, do nothing.\n \n // Return the (unchanged) root node pointer\n return root;\n}\n```\n\n```csharp\n///

\n/// Inserts a new value into the BST.\n/// Returns the root of the (potentially modified) subtree.\n///

\npublic Node Insert(Node root, int val) {\n // Base Case: We found the empty spot. Create the new\n // node and return it to be linked by its parent.\n if (root == null) {\n return new Node(val);\n }\n \n // Recursive Step: Go left or right\n if (val < root.val) {\n // Set the left child to be the result of inserting\n // into the left subtree\n root.left = Insert(root.left, val);\n } else if (val > root.val) {\n // Set the right child to be the result of inserting\n // into the right subtree\n root.right = Insert(root.right, val);\n }\n // else (val == root.val): value already exists, do nothing.\n \n // Return the (unchanged) root node pointer\n return root;\n}\n```\n\n```go\n/*\n * Inserts a new value into the BST.\n * Returns the root of the (potentially modified) subtree.\n */\nfunc (b *BST) insert(root *Node, val int) *Node {\n // Base Case: We found the empty spot. Create the new\n // node and return it to be linked by its parent.\n if root == nil {\n return NewNode(val)\n }\n \n // Recursive Step: Go left or right\n if val < root.val {\n // Set the left child to be the result of inserting\n // into the left subtree\n root.left = b.insert(root.left, val)\n } else if val > root.val {\n // Set the right child to be the result of inserting\n // into the right subtree\n root.right = b.insert(root.right, val)\n }\n // else (val == root.val): value already exists, do nothing.\n \n // Return the (unchanged) root node pointer\n return root\n}\n```\n\n```rust\npub struct Node {\n pub val: i32,\n pub left: Option>,\n pub right: Option>,\n}\n\nimpl Node {\n pub fn new(val: i32) -> Self {\n Self {\n val,\n left: None,\n right: None,\n }\n }\n}\n\npub struct Solution;\n\nimpl Solution {\n /**\n * Inserts a new value into the BST.\n * Returns the root of the (potentially modified) subtree.\n */\n pub fn insert(root: Option>, val: i32) -> Option> {\n // Base Case: We found the empty spot. Create the new\n // node and return it to be linked by its parent.\n if root.is_none() {\n return Some(Box::new(Node::new(val)));\n }\n\n let mut root = root.unwrap();\n\n // Recursive Step: Go left or right\n if val < root.val {\n // Set the left child to be the result of inserting\n // into the left subtree\n root.left = Self::insert(root.left, val);\n } else if val > root.val {\n // Set the right child to be the result of inserting\n // into the right subtree\n root.right = Self::insert(root.right, val);\n }\n // else (val == root.val): value already exists, do nothing.\n\n // Return the (unchanged) root node pointer\n Some(root)\n }\n}\n```\n\n```javascript\n/**\n * Inserts a new value into the BST.\n * Returns the root of the (potentially modified) subtree.\n */\ninsert(root, val) {\n // Base Case: We found the empty spot. Create the new\n // node and return it to be linked by its parent.\n if (root === null) {\n return new Node(val);\n }\n \n // Recursive Step: Go left or right\n if (val < root.val) {\n // Set the left child to be the result of inserting\n // into the left subtree\n root.left = this.insert(root.left, val);\n } else if (val > root.val) {\n // Set the right child to be the result of inserting\n // into the right subtree\n root.right = this.insert(root.right, val);\n }\n // else (val === root.val): value already exists, do nothing.\n \n // Return the (unchanged) root node pointer\n return root;\n}\n```\n\n```typescript\n/**\n * Inserts a new value into the BST.\n * Returns the root of the (potentially modified) subtree.\n */\nprivate insert(root: Node | null, val: number): Node {\n // Base Case: We found the empty spot. Create the new\n // node and return it to be linked by its parent.\n if (root === null) {\n return new Node(val);\n }\n \n // Recursive Step: Go left or right\n if (val < root.val) {\n // Set the left child to be the result of inserting\n // into the left subtree\n root.left = this.insert(root.left, val);\n } else if (val > root.val) {\n // Set the right child to be the result of inserting\n // into the right subtree\n root.right = this.insert(root.right, val);\n }\n // else (val === root.val): value already exists, do nothing.\n \n // Return the (unchanged) root node pointer\n return root;\n}\n```\n\n\n**Example:**\n\nInsert `25` into the earlier tree.\n\n- Start at 50 → go left to 30 → go left again to 20.\n- At `20` go **right** (to `null`).\n- The call `insert(null, 25)` hits the base case. It creates `Node(25)` and returns it.\n- This returned node is assigned as the `right` child of `20`.\n\n\n\n\nThe complexity is identical to **Search**:\n\n- **Average case:** O(log n)\n- **Worst case:** O(n)\n\n### 3. Deletion\n\nDeletion is the most complex operation because we must remove a node while ensuring the BST property (`left < parent < right`) is maintained for the *entire* tree.\n\nThere are three distinct cases to handle.\n\n#### Case 1: The Node is a Leaf (0 Children)\n\nThis is the simplest case. Remove the node by setting its parent's pointer to `null`.\n\n**Example:** To delete `20`, set `30.left = null`.\n\n#### Case 2: The Node has One Child\n\nThis is also simple. We \"bypass\" the node by linking its parent directly to its only child. \n\n**Example:** if `60` had a child `65`, we'd delete `60` by setting `70.left = 65`.\n\n#### Case 3: The Node has Two Children\n\nThis case is harder. Removing the node directly would leave two orphan subtrees.\n\nThe solution is to:\n\n1. Find a replacement node from one of its subtrees. The standard choice is the **inorder successor** (the smallest value in the node's **right** subtree).\n2. Copy the successor's *value* into the node we want to delete.\n3. Now, delete the *original* successor node from the right subtree. This deletion is guaranteed to be a simple Case 1 or Case 2, because the successor (smallest node) cannot have a left child.\n\nHere's what the delete code looks like:\n\n1. If `root` is `null`, the value isn't here to delete. Return `null`.\n2. If `val < root.val`, the node to delete is in the left subtree. Recursively call `delete` on `root.left` and assign the result back to `root.left`.\n3. If `val > root.val`, the node is in the right subtree. Recursively call `delete` on `root.right` and assign the result back to `root.right`.\n4. Otherwise, we've found the node (`root.val == val`). Now we handle the three cases:\n - If `root.left` is `null`, we bypass the current node by returning `root.right`. (This covers a leaf node, where `root.right` is also `null`, and a node with one right child.)\n - Else, if `root.right` is `null`, we bypass the current node by returning `root.left`.\n - **Case 3 (2 children):**\n\n a. Find the **inorder successor** (the smallest node in the right subtree) using the `findMin(root.right)` helper.\n\n b. Copy the `successor.val` into the current node (`root.val = successor.val`).\n\n c. Recursively call `delete` on the **right subtree** to remove the *original* successor node (passing `successor.val`). Assign the result back to `root.right`.\n\n1. Return the `root` (which may be unchanged, may have a new value, or may be replaced by a child) up the call stack.\n\n\n```java\npublic Node delete(Node root, int val) {\n // Base Case: Value not found\n if (root == null) {\n return null;\n }\n\n // --- 1. Find the node to delete ---\n if (val < root.val) {\n root.left = delete(root.left, val);\n } else if (val > root.val) {\n root.right = delete(root.right, val);\n } else {\n // --- 2. Found the node! (root.val == val) ---\n\n // Case 1: No child or Case 2: One child\n if (root.left == null) {\n return root.right; // Promote right child\n } else if (root.right == null) {\n return root.left; // Promote left child\n }\n\n // Case 3: Two children\n // Find the inorder successor (smallest value in the right subtree)\n Node successor = findMin(root.right);\n \n // Copy the successor's value to this node\n root.val = successor.val;\n \n // Recursively delete the original successor node\n // from the right subtree\n root.right = delete(root.right, successor.val);\n }\n return root;\n}\n\n/** Helper function to find the smallest node in a given subtree */\nprivate Node findMin(Node node) {\n while (node.left != null) {\n node = node.left;\n }\n return node;\n}\n```\n\n```python\ndef delete(self, root: Node, val: int) -> Node:\n # Base Case: Value not found\n if root is None:\n return None\n \n # --- 1. Find the node to delete ---\n if val < root.val:\n root.left = self.delete(root.left, val)\n elif val > root.val:\n root.right = self.delete(root.right, val)\n else:\n # --- 2. Found the node! (root.val == val) ---\n \n # Case 1: No child or Case 2: One child\n if root.left is None:\n return root.right # Promote right child\n elif root.right is None:\n return root.left # Promote left child\n \n # Case 3: Two children\n # Find the inorder successor (smallest value in the right subtree)\n successor = self._findMin(root.right)\n \n # Copy the successor's value to this node\n root.val = successor.val\n \n # Recursively delete the original successor node\n # from the right subtree\n root.right = self.delete(root.right, successor.val)\n \n return root\n\ndef _findMin(self, node: Node) -> Node:\n \"\"\"Helper function to find the smallest node in a given subtree\"\"\"\n while node.left is not None:\n node = node.left\n return node\n```\n\n```cpp\nNode* deleteNode(Node* root, int val) {\n // Base Case: Value not found\n if (root == nullptr) {\n return nullptr;\n }\n\n // --- 1. Find the node to delete ---\n if (val < root->val) {\n root->left = deleteNode(root->left, val);\n } else if (val > root->val) {\n root->right = deleteNode(root->right, val);\n } else {\n // --- 2. Found the node! (root->val == val) ---\n\n // Case 1: No child or Case 2: One child\n if (root->left == nullptr) {\n Node* rightChild = root->right;\n delete root;\n return rightChild; // Promote right child\n } else if (root->right == nullptr) {\n Node* leftChild = root->left;\n delete root;\n return leftChild; // Promote left child\n }\n\n // Case 3: Two children\n // Find the inorder successor (smallest value in the right subtree)\n Node* successor = findMin(root->right);\n\n // Copy the successor's value to this node\n root->val = successor->val;\n\n // Recursively delete the original successor node\n // from the right subtree\n root->right = deleteNode(root->right, successor->val);\n }\n return root;\n}\n\n/** Helper function to find the smallest node in a given subtree */\nNode* findMin(Node* node) {\n while (node->left != nullptr) {\n node = node->left;\n }\n return node;\n}\n```\n\n```csharp\npublic Node Delete(Node root, int val) {\n // Base Case: Value not found\n if (root == null) {\n return null;\n }\n \n // --- 1. Find the node to delete ---\n if (val < root.val) {\n root.left = Delete(root.left, val);\n } else if (val > root.val) {\n root.right = Delete(root.right, val);\n } else {\n // --- 2. Found the node! (root.val == val) ---\n \n // Case 1: No child or Case 2: One child\n if (root.left == null) {\n return root.right; // Promote right child\n } else if (root.right == null) {\n return root.left; // Promote left child\n }\n \n // Case 3: Two children\n // Find the inorder successor (smallest value in the right subtree)\n Node successor = FindMin(root.right);\n \n // Copy the successor's value to this node\n root.val = successor.val;\n \n // Recursively delete the original successor node\n // from the right subtree\n root.right = Delete(root.right, successor.val);\n }\n return root;\n}\n\n///

Helper function to find the smallest node in a given subtree

\nprivate Node FindMin(Node node) {\n while (node.left != null) {\n node = node.left;\n }\n return node;\n}\n```\n\n```go\nfunc (b *BST) deleteNode(root *Node, val int) *Node {\n // Base Case: Value not found\n if root == nil {\n return nil\n }\n \n // --- 1. Find the node to delete ---\n if val < root.val {\n root.left = b.deleteNode(root.left, val)\n } else if val > root.val {\n root.right = b.deleteNode(root.right, val)\n } else {\n // --- 2. Found the node! (root.val == val) ---\n \n // Case 1: No child or Case 2: One child\n if root.left == nil {\n return root.right // Promote right child\n } else if root.right == nil {\n return root.left // Promote left child\n }\n \n // Case 3: Two children\n // Find the inorder successor (smallest value in the right subtree)\n successor := b.findMin(root.right)\n \n // Copy the successor's value to this node\n root.val = successor.val\n \n // Recursively delete the original successor node\n // from the right subtree\n root.right = b.deleteNode(root.right, successor.val)\n }\n return root\n}\n\n// Helper function to find the smallest node in a given subtree\nfunc (b *BST) findMin(node *Node) *Node {\n for node.left != nil {\n node = node.left\n }\n return node\n}\n```\n\n```rust\npub struct Node {\n pub val: i32,\n pub left: Option>,\n pub right: Option>,\n}\n\nimpl Node {\n pub fn new(val: i32) -> Self {\n Self {\n val,\n left: None,\n right: None,\n }\n }\n}\n\npub struct Solution;\n\nimpl Solution {\n pub fn delete(root: Option>, val: i32) -> Option> {\n Self::delete_node(root, val)\n }\n\n fn delete_node(root: Option>, val: i32) -> Option> {\n // Base Case: Value not found\n let mut root = match root {\n Some(node) => node,\n None => return None,\n };\n\n // --- 1. Find the node to delete ---\n if val < root.val {\n root.left = Self::delete_node(root.left, val);\n } else if val > root.val {\n root.right = Self::delete_node(root.right, val);\n } else {\n // --- 2. Found the node! (root.val == val) ---\n\n // Case 1: No child or Case 2: One child\n if root.left.is_none() {\n return root.right; // Promote right child\n } else if root.right.is_none() {\n return root.left; // Promote left child\n }\n\n // Case 3: Two children\n // Find the inorder successor (smallest value in the right subtree)\n let successor_val = Self::find_min(root.right.as_ref().unwrap()).val;\n\n // Copy the successor's value to this node\n root.val = successor_val;\n\n // Recursively delete the original successor node\n // from the right subtree\n root.right = Self::delete_node(root.right, successor_val);\n }\n Some(root)\n }\n\n /// Helper function to find the smallest node in a given subtree\n fn find_min(mut node: &Node) -> &Node {\n while let Some(ref left) = node.left {\n node = left.as_ref();\n }\n node\n }\n}\n```\n\n```javascript\ndelete(root, val) {\n // Base Case: Value not found\n if (root === null) {\n return null;\n }\n \n // --- 1. Find the node to delete ---\n if (val < root.val) {\n root.left = this.delete(root.left, val);\n } else if (val > root.val) {\n root.right = this.delete(root.right, val);\n } else {\n // --- 2. Found the node! (root.val === val) ---\n \n // Case 1: No child or Case 2: One child\n if (root.left === null) {\n return root.right; // Promote right child\n } else if (root.right === null) {\n return root.left; // Promote left child\n }\n \n // Case 3: Two children\n // Find the inorder successor (smallest value in the right subtree)\n const successor = this.findMin(root.right);\n \n // Copy the successor's value to this node\n root.val = successor.val;\n \n // Recursively delete the original successor node\n // from the right subtree\n root.right = this.delete(root.right, successor.val);\n }\n return root;\n}\n\n/** Helper function to find the smallest node in a given subtree */\nfindMin(node) {\n while (node.left !== null) {\n node = node.left;\n }\n return node;\n}\n```\n\n```typescript\nprivate delete(root: Node | null, val: number): Node | null {\n // Base Case: Value not found\n if (root === null) {\n return null;\n }\n \n // --- 1. Find the node to delete ---\n if (val < root.val) {\n root.left = this.delete(root.left, val);\n } else if (val > root.val) {\n root.right = this.delete(root.right, val);\n } else {\n // --- 2. Found the node! (root.val === val) ---\n \n // Case 1: No child or Case 2: One child\n if (root.left === null) {\n return root.right; // Promote right child\n } else if (root.right === null) {\n return root.left; // Promote left child\n }\n \n // Case 3: Two children\n // Find the inorder successor (smallest value in the right subtree)\n const successor = this.findMin(root.right);\n \n // Copy the successor's value to this node\n root.val = successor.val;\n \n // Recursively delete the original successor node\n // from the right subtree\n root.right = this.delete(root.right, successor.val);\n }\n return root;\n}\n\n/** Helper function to find the smallest node in a given subtree */\nprivate findMin(node: Node): Node {\n while (node.left !== null) {\n node = node.left;\n }\n return node;\n}\n```\n\n\n**Example: Delete **`50`\n\n1. `delete(root, 50)` is called. The `else` block (Step 4) is hit.\n2. `root.left` (30) and `root.right` (70) are not `null`. This is Case 3.\n3. `findMin(root.right)` is called on node `70`. It goes left and finds `60`.\n4. `successor` is node `60`.\n5. `root.val = successor.val;` (The root node, formerly holding `50`, now holds `60`. The root *node object* is unchanged; only its value is overwritten.)\n6. `delete(root.right, 60)` is called to remove the original `60`.\n7. This recursive call finds `60`. `60.left` is `null`, so it hits Case 1/2 and returns `60.right` (which is `null`).\n8. `70.left` is set to `null`.\n9. The same root node is returned, now holding the value `60` instead of `50`.\n\nThe time complexity of delete is O(log n) on average if the tree is balanced, and O(n) in the worst case for a skewed tree.\n\n---\n\n# Built-in Libraries\n\nYou rarely write a BST from scratch in practice. Most languages ship a sorted map and sorted set as part of their standard library, and these are the right starting point whenever a problem needs ordered keys, range queries, or `O(log n)` predecessor/successor lookups.\n\nAn important point: every production \"BST\" in standard libraries is a **self-balancing variant**. The standard implementations use:\n\n- **Red-black trees**: Java's `TreeMap`, C++'s `std::map`, C#'s `SortedDictionary`.\n- **B-trees**: Rust's `BTreeMap`, designed for cache locality at the cost of slightly more complex code.\n- A plain unbalanced BST is never used as a built-in container because adversarial insertion orders would degrade it to O(n).\n\nThe API stays the same in either case: insert, lookup, delete, and ordered traversal in `O(log n)`.\n\n\n#### Java\n\n`TreeMap` and `TreeSet` (in `java.util`) are red-black tree implementations. Keys are kept in sorted order, and the API exposes navigation methods like `floorKey`, `ceilingKey`, `higherKey`, and `lowerKey` for predecessor/successor queries.\n\n\n```java\nTreeMap map = new TreeMap<>();\nmap.put(50, \"fifty\");\nmap.put(30, \"thirty\");\nmap.put(70, \"seventy\");\n\nmap.firstKey(); // 30 (smallest)\nmap.lastKey(); // 70 (largest)\nmap.floorKey(40); // 30 (largest key <= 40)\nmap.ceilingKey(40); // 50 (smallest key >= 40)\nmap.subMap(30, 70); // view of keys in [30, 70)\n\nTreeSet set = new TreeSet<>();\nset.add(50); set.add(30); set.add(70);\nset.first(); // 30\n```\n\n\n\nFor interview problems where the input fits in memory and the language has a built-in sorted map, use it. The implementation work is only meaningful when the problem explicitly asks you to write a balanced BST or when you need a structure the standard library doesn't offer (a treap with random rotations, an order-statistic tree, etc.).\n\n---\n\nThis unbalanced worst case is exactly the problem that **self-balancing BSTs** (AVL trees, red-black trees) solve.\n\n---\n\n# Quiz","pageType":"dsa"}

Introduction to BST

Get Premium