Visualizers

Binary Search Tree Visualizer

Interactive BST displaying insertion, deletion, and searching.

native (SVG) Client-side

Ready. Type a number and click Insert, Delete or Search.

Execution Log

Tree Height: 0

Total Nodes: 0

Current Action:

Idle

Legend:

Standard Node

Active Traversal Path

Target Found / Inserted

Binary Search Tree (BST) Operations

A Binary Search Tree is a node-based binary tree data structure where each node has at most two children. It keeps its keys in sorted order, which allows for fast lookups, additions, and deletions.

BST Properties

For any given node in a BST:

The left subtree of a node contains only nodes with keys less than the node's key.
The right subtree of a node contains only nodes with keys greater than the node's key.
The left and right subtrees must each also be a binary search tree.

Implementation

class Node {
  constructor(val) {
    this.val = val;
    this.left = null;
    this.right = null;
  }
}

class BST {
  constructor() {
    this.root = null;
  }

  insert(val) {
    this.root = this._insert(this.root, val);
  }
  _insert(node, val) {
    if (!node) return new Node(val);
    if (val < node.val) node.left = this._insert(node.left, val);
    else if (val > node.val) node.right = this._insert(node.right, val);
    return node;
  }

  search(val) {
    return this._search(this.root, val);
  }
  _search(node, val) {
    if (!node || node.val === val) return node;
    if (val < node.val) return this._search(node.left, val);
    return this._search(node.right, val);
  }
}

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

class BST:
    def __init__(self):
        self.root = None

    def insert(self, val):
        self.root = self._insert(self.root, val)
        
    def _insert(self, node, val):
        if not node:
            return Node(val)
        if val < node.val:
            node.left = self._insert(node.left, val)
        elif val > node.val:
            node.right = self._insert(node.right, val)
        return node

    def search(self, val):
        return self._search(self.root, val)
        
    def _search(self, node, val):
        if not node or node.val == val:
            return node
        if val < node.val:
            return self._search(node.left, val)
        return self._search(node.right, val)

public class BST {
    static class Node {
        int val;
        Node left, right;
        Node(int val) {
            this.val = val;
            this.left = this.right = null;
        }
    }

    private Node root = null;

    public void insert(int val) {
        root = insertRec(root, val);
    }
    private Node insertRec(Node node, int val) {
        if (node == null) return new Node(val);
        if (val < node.val) node.left = insertRec(node.left, val);
        else if (val > node.val) node.right = insertRec(node.right, val);
        return node;
    }

    public Node search(int val) {
        return searchRec(root, val);
    }
    private Node searchRec(Node node, int val) {
        if (node == null || node.val == val) return node;
        if (val < node.val) return searchRec(node.left, val);
        return searchRec(node.right, val);
    }
}

struct Node {
    int val;
    Node* left = nullptr;
    Node* right = nullptr;
    Node(int x) : val(x) {}
};

class BST {
private:
    Node* root = nullptr;

    Node* insertRec(Node* node, int val) {
        if (!node) return new Node(val);
        if (val < node->val) node->left = insertRec(node->left, val);
        else if (val > node->val) node->right = insertRec(node->right, val);
        return node;
    }

    Node* searchRec(Node* node, int val) {
        if (!node || node->val == val) return node;
        if (val < node->val) return searchRec(node->left, val);
        return searchRec(node->right, val);
    }

public:
    void insert(int val) {
        root = insertRec(root, val);
    }

    Node* search(int val) {
        return searchRec(root, val);
    }
};

Related Tools

Big-O Visualizer

Interactive growth-curve chart for common complexity classes.

Data Structure Visualizer

Animated operations on linked lists, trees, stacks and hash tables.

Algorithm Visualizer

Step-through animations for sorting and pathfinding algorithms.