Algorithm Guidecomplexity: Avg O(log n)

Binary Search Tree (BST)

A binary tree that keeps the rule left child < parent < right child. Its sorted structure gives average O(log n) search, insert, and delete, but it degrades to O(n) if it becomes lopsided.

01Binary Search Tree (BST)

Explore How It Works

Binary search tree (BST). Values are inserted by the rule: smaller on the left, larger on the right.

Insert 30 · Since 30 < 50, go down to the root's left and settle there.

Insert 70 · Since 70 > 50, go down to the right and settle there.

Insert 20 · 20 < 50 (left), 20 < 30 (left). Descend twice to settle.

Insert 40 · 40 < 50 (left), 40 > 30 (right). Descend to settle.

Insert 60 · 60 > 50 (right), 60 < 70 (left). Descend to settle.

search(40) · Left at 50, right at 30 — 40 is found in just two steps.

Thanks to the ordering rule, each comparison skips an entire branch — fast at an average O(log n).

Live Python

1class Node:

2 def __init__(self, key):

3 self.key = key

4 self.left = None

5 self.right = None

7def insert(root, key):

8 if root is None:

# root = 50

9 return Node(key)

10 if key < root.key:

11 root.left = insert(root.left, key)

12 elif key > root.key:

13 root.right = insert(root.right, key)

14 return root

16def search(root, key):

17 while root and root.key != key:

18 root = root.left if key < root.key else root.right

19 return root

1 / 8

02 Understand It Simply

For Everyone

🔑How It Works

Smaller values go left, larger values go right. Every comparison halves the range still worth searching.

💡In Plain Words

A branching structure with smaller values on the left and larger on the right.

That rule lets you skip half the data on each step, so lookups are fast (average O(log n)).

📍Where It's Used

–Fast search/insert on sorted data
–range queries
–autocomplete dictionaries

03 Python Implementation

A clean, readable reference implementation of the core logic of Binary Search Tree (BST).

core_implementation.py

class Node:
    def __init__(self, key):
        self.key = key
        self.left = None
        self.right = None

def insert(root, key):
    if root is None:
        return Node(key)
    if key < root.key:
        root.left = insert(root.left, key)
    elif key > root.key:
        root.right = insert(root.right, key)
    return root

def search(root, key):
    while root and root.key != key:
        root = root.left if key < root.key else root.right
    return root

04 Frequently Asked Questions

FAQ

What is Binary Search Tree (BST)?+

A binary tree that keeps the rule left child < parent < right child. Its sorted structure gives average O(log n) search, insert, and delete, but it degrades to O(n) if it becomes lopsided.

What is the time complexity of Binary Search Tree (BST)?+

The time complexity of Binary Search Tree (BST) is Avg O(log n). Follow the step-by-step visualization to see exactly why.

Where is Binary Search Tree (BST) used?+

Fast search/insert on sorted data, range queries, autocomplete dictionaries.

What's a simple analogy for Binary Search Tree (BST)?+

Smaller values go left, larger values go right. Every comparison halves the range still worth searching.

→ Data Structures — see allRelated