Ugenz Academy/Tutorial

Bst

12 min read2,241 words

Reading progress

Keep learning

Binary Search Tree (BST)

A Binary Search Tree (BST) is a special type of Binary Tree where nodes are arranged in a specific order.

The main idea is:

Left subtree < Root < Right subtree

This ordering makes searching, insertion, and deletion much more efficient than in a normal binary tree—especially when the tree is balanced.

1. What is a BST?

Consider this tree:

50 / \ 30 70 / \ / \ 20 40 60 80

For every node:

  • Values on the left are smaller.
  • Values on the right are larger.

For example:

50 / \ < 50 > 50

At node 30:

30 / \ < 30 > 30

At node 70:

70 / \ < 70 > 70

This rule applies recursively to every subtree.

2. BST vs Binary Tree

This is very important.

Binary Tree

A binary tree only says:

Each node can have at most two children.

Example:

50 / \ 80 20

This is a valid binary tree.

But it is not a BST because:

80 > 50

yet 80 is on the left.

BST

A BST additionally requires:

Left < Root < Right

Example:

50 / \ 30 70

This is both a binary tree and a BST.

3. BST Node in C++

A BST node is similar to a normal binary-tree node.

struct Node { int data; Node* left; Node* right; Node(int value) { data = value; left = nullptr; right = nullptr; } };

4. Creating a BST

Suppose we want to insert:

50, 30, 70, 20, 40, 60, 80

The final tree becomes:

50 / \ 30 70 / \ / \ 20 40 60 80

5. Insertion in BST

This is one of the most important BST operations.

Suppose we want to insert 40.

Start at root:

40 vs 50

Since:

40 < 50

go left.

50 / 30

Now:

40 > 30

go right.

50 / 30 \ 40

40 finds an empty position, so insert it there.

C++ insertion

Node* insert(Node* root, int value) { if (root == nullptr) { return new Node(value); } if (value < root->data) { root->left = insert(root->left, value); } else if (value > root->data) { root->right = insert(root->right, value); } return root; }

Example

Node* root = nullptr; root = insert(root, 50); root = insert(root, 30); root = insert(root, 70); root = insert(root, 20); root = insert(root, 40); root = insert(root, 60); root = insert(root, 80);

Result:

50 / \ 30 70 / \ / \ 20 40 60 80

6. Searching in BST

This is where BST becomes powerful.

Suppose we want to find:

60

Start at 50.

60 > 50

So we only go right.

50 \ 70

Now:

60 < 70

So go left.

70 / 60

Found!

We didn't need to check every node.

C++ Search

bool search(Node* root, int target) { if (root == nullptr) { return false; } if (root->data == target) { return true; } if (target < root->data) { return search(root->left, target); } return search(root->right, target); }

Usage:

if (search(root, 60)) { cout << "Found"; } else { cout << "Not Found"; }

7. Why BST Search is Faster

Imagine:

50 / \ 30 70 / \ / \ 20 40 60 80

Searching for 60:

50 ↓ 70 ↓ 60

Only 3 nodes were visited.

We eliminated half of the possible directions at each step.

This is similar to the idea behind binary search.

8. Minimum Value in BST

In a BST:

The minimum value is the leftmost node.

Example:

50 / \ 30 70 / 20

Keep moving left:

50 → 30 → 20

So:

Minimum = 20

C++

Node* findMin(Node* root) { if (root == nullptr) { return nullptr; } while (root->left != nullptr) { root = root->left; } return root; }

9. Maximum Value in BST

Similarly:

The maximum value is the rightmost node.

50 / \ 30 70 \ 80

Move right:

50 → 70 → 80

Therefore:

Maximum = 80

C++

Node* findMax(Node* root) { if (root == nullptr) { return nullptr; } while (root->right != nullptr) { root = root->right; } return root; }

10. Inorder Traversal of BST

This is extremely important.

For a binary tree:

Inorder = Left → Root → Right

For a BST, inorder traversal produces values in sorted order.

Example:

50 / \ 30 70 / \ / \ 20 40 60 80

Inorder:

20 30 40 50 60 70 80

Notice:

20 < 30 < 40 < 50 < 60 < 70 < 80

Therefore:

Inorder traversal of a BST gives sorted order.

C++

void inorder(Node* root) { if (root == nullptr) { return; } inorder(root->left); cout << root->data << " "; inorder(root->right); }

11. Deletion in BST

Deletion is the most important and slightly difficult BST operation.

There are 3 cases.

Case 1: Delete a Leaf Node

A leaf has no children.

Example:

50 / \ 30 70 / \ 20 40

Delete 20.

Since 20 has no children:

50 / \ 30 70 \ 40

Simply remove it.

Case 2: Delete a Node With One Child

Example:

50 / 30 / 20

Delete 30.

30 has one child:

20

So connect 50 directly to 20.

50 / 20

The child takes the deleted node's position.

Case 3: Delete a Node With Two Children ⭐

This is the important case.

Consider:

50 / \ 30 70 / \ / \ 20 40 60 80

Delete:

50

It has two children.

We need a replacement.

We can use either:

Inorder successor

The smallest value in the right subtree.

Right subtree:

70 / \ 60 80

Smallest value = 60.

So replace 50 with 60.

60 / \ 30 70 / \ \ 20 40 80

Or inorder predecessor

The largest value in the left subtree.

Left subtree:

30 / \ 20 40

Largest value = 40.

Both methods can work.

12. BST Delete Code

Node* deleteNode(Node* root, int key) { if (root == nullptr) { return nullptr; } // Search for the node if (key < root->data) { root->left = deleteNode(root->left, key); } else if (key > root->data) { root->right = deleteNode(root->right, key); } // Node found else { // Case 1: No child if (root->left == nullptr && root->right == nullptr) { delete root; return nullptr; } // Case 2: Only right child if (root->left == nullptr) { Node* temp = root->right; delete root; return temp; } // Case 2: Only left child if (root->right == nullptr) { Node* temp = root->left; delete root; return temp; } // Case 3: Two children Node* temp = findMin(root->right); root->data = temp->data; root->right = deleteNode(root->right, temp->data); } return root; }

This handles all three cases.

13. Complete BST Example

#include <iostream> using namespace std; struct Node { int data; Node* left; Node* right; Node(int value) { data = value; left = nullptr; right = nullptr; } }; Node* insert(Node* root, int value) { if (root == nullptr) { return new Node(value); } if (value < root->data) { root->left = insert(root->left, value); } else if (value > root->data) { root->right = insert(root->right, value); } return root; } bool search(Node* root, int target) { if (root == nullptr) { return false; } if (root->data == target) { return true; } if (target < root->data) { return search(root->left, target); } return search(root->right, target); } void inorder(Node* root) { if (root == nullptr) { return; } inorder(root->left); cout << root->data << " "; inorder(root->right); } Node* findMin(Node* root) { while (root->left != nullptr) { root = root->left; } return root; } Node* deleteNode(Node* root, int key) { if (root == nullptr) { return nullptr; } if (key < root->data) { root->left = deleteNode(root->left, key); } else if (key > root->data) { root->right = deleteNode(root->right, key); } else { if (root->left == nullptr) { Node* temp = root->right; delete root; return temp; } if (root->right == nullptr) { Node* temp = root->left; delete root; return temp; } Node* temp = findMin(root->right); root->data = temp->data; root->right = deleteNode(root->right, temp->data); } return root; } int main() { Node* root = nullptr; root = insert(root, 50); root = insert(root, 30); root = insert(root, 70); root = insert(root, 20); root = insert(root, 40); root = insert(root, 60); root = insert(root, 80); cout << "Inorder: "; inorder(root); cout << "\n"; cout << "Search 60: "; if (search(root, 60)) cout << "Found"; else cout << "Not Found"; root = deleteNode(root, 50); cout << "\nAfter deleting 50: "; inorder(root); return 0; }

Output:

Inorder: 20 30 40 50 60 70 80 Search 60: Found After deleting 50: 20 30 40 60 70 80

14. BST Complexity ⭐

Let h = height of the tree.

OperationAverage / BalancedWorst Case
SearchO(log n)O(n)
InsertO(log n)O(n)
DeleteO(log n)O(n)
MinimumO(log n)O(n)
MaximumO(log n)O(n)
Inorder traversalO(n)O(n)

Why can it become O(n)?

Because a BST can become skewed.

15. Balanced BST

Good BST:

50 / \ 30 70 / \ / \ 20 40 60 80

Height is relatively small.

Searching is approximately:

O(log n)

16. Skewed BST ⚠️

Suppose we insert values in this order:

10 20 30 40 50 60

The tree becomes:

10 \ 20 \ 30 \ 40 \ 50 \ 60

It looks like a linked list.

Now searching for 60 requires:

10 → 20 → 30 → 40 → 50 → 60

Therefore:

O(n)

So a normal BST does not guarantee O(log n).

17. BST vs Binary Search

Don't confuse these two.

Binary Search

Algorithm used mainly on a sorted array:

[10, 20, 30, 40, 50, 60]

It repeatedly checks the middle.

Complexity:

O(log n)

Binary Search Tree

A data structure where values are organized:

40 / \ 20 60

Search follows left/right pointers.

Balanced BST:

O(log n)

Worst case:

O(n)

18. BST vs Heap

These are also different.

BST

Left < Root < Right

Example:

50 / \ 30 70

Used for:

  • Searching
  • Ordered data
  • Finding predecessor/successor
  • Maintaining sorted data

Heap

A heap is usually a complete binary tree.

Min-heap:

10 / \ 20 30

Parent is smaller than children.

Used for:

  • Priority queues
  • Finding minimum/maximum quickly
  • Heap sort

19. Important BST Properties

Remember these:

Property 1

Left subtree < Root

Property 2

Right subtree > Root

Property 3

The rule applies recursively to every subtree.

Property 4 ⭐

Inorder traversal → Sorted order

Property 5

Minimum:

Leftmost node

Property 6

Maximum:

Rightmost node

Property 7

Balanced BST operations:

Search → O(log n) Insert → O(log n) Delete → O(log n)

Property 8

Worst-case skewed BST:

Search → O(n) Insert → O(n) Delete → O(n)

20. Real-Life Analogy

Imagine a dictionary arranged alphabetically.

You want to find:

"Computer"

You don't start from the first word and check every word.

You use ordering to decide:

Too early? → Go right Too late? → Go left

A BST uses a similar idea:

Target < current → LEFT Target > current → RIGHT Target == current → FOUND

21. Most Important BST Problems

After learning the basic operations, common interview/DSA problems include:

  1. Search in BST
  2. Insert into BST
  3. Delete from BST
  4. Find minimum
  5. Find maximum
  6. Validate a BST
  7. Find height of BST
  8. Find kth smallest element
  9. Find kth largest element
  10. Find inorder successor
  11. Find inorder predecessor
  12. Lowest Common Ancestor (LCA)
  13. Convert sorted array to BST
  14. Balance a BST
  15. Two Sum in BST
  16. Recover a corrupted BST

🧠 Final Mental Model

Think of a BST like this:

BST | ---------------- | | Left side Right side smaller larger | | -------- Root -- | Search/Insert left or right

The three most important things to remember are:

1. Left < Root < Right 2. Inorder traversal = Sorted order 3. Balanced BST: Search / Insert / Delete = O(log n)

And the roadmap now becomes:

Trees ↓ Binary Tree ↓ BST ↓ Heap ↓ Priority Queue ↓ Trie

Keep learning. Keep building. Keep growing.

© 2026 Ugenz Academy