Binary Search Tree

DSA · Trees

Theory

A binary search tree (BST) is a binary tree where every node's left subtree holds smaller values and its right subtree holds larger values. This ordering lets search, insert and delete follow a single path from the root, taking O(h) time. A balanced BST has height O(log n), but inserting sorted data into a plain BST creates a chain of height n, so operations degrade to O(n). In-order traversal of a BST returns the values in sorted order.

Why we use it

BSTs keep data sorted while supporting fast inserts and searches, plus range queries and min/max.

When to use it

Use BSTs (usually balanced ones, such as TreeMap, red-black trees or B-trees in databases) when you need sorted data with frequent updates.

How it works

  1. Start at root
  2. Node is None? Yes: Insert here / not found. No: Compare key with node.
  3. key == node.key? Yes: Found. No: Go left if smaller, right if larger.
  4. O(h) per operation, h = height

Syntax

search(n, x):
    if n is None or n.val == x: return n
    return search(n.left, x) if x < n.val else search(n.right, x)

Search/Insert/Delete: O(h)   Balanced h = O(log n)

Example

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

def insert(root, val):
    if root is None:
        return Node(val)
    if val < root.val:
        root.left = insert(root.left, val)
    else:
        root.right = insert(root.right, val)
    return root

def search(root, val):
    steps = 0
    while root:
        steps += 1
        if val == root.val:
            return True, steps
        root = root.left if val < root.val else root.right
    return False, steps

def inorder(n):
    return inorder(n.left) + [n.val] + inorder(n.right) if n else []

root = None
for v in [50, 30, 70, 20, 40, 60, 80]:
    root = insert(root, v)
print("Sorted:", inorder(root))
print("Search 60:", search(root, 60))
print("Search 65:", search(root, 65))

Key points

DSA topics

Introduction to DSA

Arrays and Searching

Sorting Algorithms

Linked Lists

Stacks and Queues

Hashing

Trees

Heaps

Graphs

Algorithm Techniques

Classic Algorithms

Dynamic Programming

T
Tech Town
Log InSign Up Free
Home SQL Python DSA Power BI Snowflake Databricks Spark Gen AI Practice Problems Contest Blog

Data Structures & Algorithms

The complete DSA roadmap: theory, why and when to use every structure and algorithm, Big O complexity, and Python code you can run right here in the browser.

{{ sectionCount }}
Sections
{{ topicCount }}
Topics
Free
Forever
Hands-on practice Practice DSA Online 251 problems across 13 patterns, with hidden tests and step-by-step optimal solutions. Start practising →
Section {{ sec.num }}

{{ sec.label }}

DSA  /  {{ current.sectionLabel }}  /  {{ current.name }}

{{ current.name }}

Theory

{{ current.def }}

Why we use it

{{ current.why }}

When to use it

{{ current.when }}

Flowchart — how {{ current.name }} works
{{ nd.text }}
{{ nd.text }}
◇ {{ nd.text }}
Yes → {{ nd.yes }}
No → {{ nd.no }}
Step-by-step visualisation
{{ cell.v }}
{{ cell.i }} {{ cell.tag }}
Step {{ vizStepLabel }}: {{ vizNote }}
■ comparing ■ swapping / moving ■ done / found ■ out of range
Complexity & Pseudocode
{{ current.syntax }}
Example Code
{{ current.example }}
▶ Try It Live — runs real Python 3 in your browser (first run loads the engine)
{{ liveOutput }}
{{ liveError }}
Key Points — click to check off as you learn
  • {{ pt.mark }} {{ pt.text }}

Share this topic