Binary Search Tree (BST)

A Binary Search Tree is a node-based data structure that maintains sorted data and allows for efficient search, insertion, and deletion operations. Each node has at most two children, with values in the left subtree being less than the parent and values in the right subtree being greater or equal.

Try the interactive visualizer: Binary Tree Visualizer

Structure

Each node in a BST contains:

value: The data stored in the node
leftChild: Pointer to the left child node (smaller values)
rightChild: Pointer to the right child node (greater or equal values)

public class Node {
    private Node leftChild;
    private Node rightChild;
    private int value;

    public Node(int value) {
        this.value = value;
    }
}

Key Operations

Insert
Search
Height

Insert Operation

Insertion in a BST follows the binary search property to find the correct position for the new value.Algorithm:

If the tree is empty, create the root node
Start from the root and compare the value
If value < current node, traverse left
If value >= current node, traverse right
Insert when an empty position is found

public void insert(int value) {
Node node = new Node(value);

if (root == null) {
    root = node;
    return;
}

Node current = root;
while (true) {
    if (value < current.value) {
        if (current.leftChild == null) {
            current.leftChild = node;
            break;
        }
        current = current.leftChild;
    } else {
        if (current.rightChild == null) {
            current.rightChild = node;
            break;
        }
        current = current.rightChild;
    }
}
}

Time Complexity: O(log n) average case, O(n) worst case (unbalanced tree)Space Complexity: O(1)

Find Operation

Searching in a BST leverages the sorted property to efficiently locate values.Algorithm:

Start from the root
Compare target value with current node
If equal, value is found
If target > current, search right subtree
If target < current, search left subtree
Return false if we reach null

public boolean find(int value) {
Node current = root;
while (current != null) {
    if (value == current.value)
        return true;
    else if (value > current.value)
        current = current.rightChild;
    else if (value < current.value)
        current = current.leftChild;
}
return false;
}

Time Complexity: O(log n) average case, O(n) worst caseSpace Complexity: O(1)

Height Calculation

The height of a tree is the longest path from root to a leaf node. This operation uses recursion to traverse both subtrees.Algorithm:

Base case: if node is null, return 0
Recursively calculate height of left subtree
Recursively calculate height of right subtree
Return 1 + max(leftHeight, rightHeight)

public int height() {
return height(root);
}

private int height(Node root) {
if (root == null)
    return 0;

return 1 + Math.max(height(root.leftChild), height(root.rightChild));
}

Time Complexity: O(n) - visits every nodeSpace Complexity: O(h) - recursive call stack, where h is height

Properties

BST Invariant

The fundamental property of BSTs:

All values in the left subtree < parent value
All values in the right subtree >= parent value
This property holds recursively for all subtrees

Performance Characteristics

Balanced BST:

Search: O(log n)
Insert: O(log n)
Delete: O(log n)
Space: O(n)

Worst Case (Unbalanced):

All operations degrade to O(n) when the tree becomes a linked list

Use Cases

Maintaining sorted data with dynamic insertions/deletions
Database indexing
File system organization
Expression parsing
Priority queues (when balanced)

Interactive Visualizer

The Binary Tree visualizer provides:

Insert: Add values and watch the tree grow dynamically
Visual feedback: See how values are placed according to BST rules
Animated operations: Understand the insertion algorithm step-by-step

Try it Live

Experiment with the interactive Binary Search Tree visualizer to see insertions in real-time

Code Implementation

The visualizer implements the BST using TypeScript with the following key features:

const insert = async (
  value: number,
  rootObj: { root: Node<number> | null },
  renderTree: () => Promise<void>
) => {
  if (!rootObj.root) {
    rootObj.root = new Node(value);
    await renderTree();
    return;
  }
  let current = rootObj.root;
  while (current) {
    if (value >= current.value) {
      if (!current.right) {
        current.right = new Node(value);
        break;
      } else current = current.right;
    } else {
      if (!current.left) {
        current.left = new Node(value);
        break;
      } else current = current.left;
    }
  }
  await renderTree();
};

Tree Traversals

Learn about different ways to traverse binary trees

General Tree

Explore general tree structures with multiple children

Linear Structures

Trees

Graphs

Hash-Based

Priority & Heap

Binary Search Tree (BST)

Binary Search Tree (BST)

Structure

Key Operations

Insert Operation

Find Operation

Height Calculation

Properties

Interactive Visualizer

Try it Live

Code Implementation

Tree Traversals

General Tree

Build docs developers (and LLMs) love

Linear Structures

Trees

Graphs

Hash-Based

Priority & Heap

​Binary Search Tree (BST)

​Structure

​Key Operations

​Insert Operation

​Find Operation

​Height Calculation

​Properties

​Interactive Visualizer

Try it Live

​Code Implementation

​Related Topics

Tree Traversals

General Tree

Build docs developers (and LLMs) love

Binary Search Tree (BST)

Structure

Key Operations

Insert Operation

Find Operation

Height Calculation

Properties

Interactive Visualizer

Code Implementation

Related Topics