What is the BST invariant?

The property that for any node, all values in its left subtree are smaller than the node, and all values in its right subtree are larger.

What is the time complexity of BST operations?

In a balanced BST, operations are O(log n). However, in the worst case (a skewed tree), they can degrade to O(n).

How to handle duplicate values in a BST?

Commonly, duplicates are either ignored or stored by convention consistently in either the left or right subtree.

Binary Search Tree

A binary search tree is a hierarchical data structure in which each node has at most two children, with left child < parent < right child.

READY

In-order output

Insert a value, or press Random for a tree to search. Every operation walks down from the root.

Value

Order

Intuition

Imagine a family tree where every parent has at most two children. In a BST, we organize numbers so that everything to the left is smaller and everything to the right is larger. This makes finding a number very fast—like looking up a word in a dictionary!

Concept

In a binary search tree, every value in a node's left subtree is smaller than the node and every value in its right subtree is larger. That one ordering rule lets a search skip an entire subtree at every step: O(log n) when the tree is balanced, but O(n) when values arrive already sorted and the tree degenerates into a line.

How it Works

Root: The top node of the tree.
Left Subtree: Contains values smaller than the root.
Right Subtree: Contains values larger than the root.
Leaf: A node with no children.

Step-by-Step Breakdown

Insert(Value):

Start at the Root.
If Value < CurrentNode.Value, go Left.
If Value > CurrentNode.Value, go Right.
If you reach an empty spot (NULL), insert the new node there.

When to Use

Fast Lookup: Searching is O(log n) on average.
Sorted Data: In-order traversal gives sorted elements.
Dynamic Data: Efficient insertions and deletions compared to arrays.

When NOT to Use

Unbalanced Trees: In worst case (skewed tree), operations become O(n).
Constant Time Access: If you need O(1) access by index (use Array).

How to Identify

Look for problems involving searching, sorting, or maintaining a dynamic sorted set of elements. Keywords: "Binary Search", "Tree", "Hierarchy", "Sorted".

AI resume checker — match your resume to the job description

Binary Tree

AVL Tree

Complexity

Time (Best)

O(log n)

Time (Average)

O(log n)

Time (Worst)

O(n)

Space

O(n)

Binary Search Tree Code

1// Javascript BST Node and Insert
2class Node {
3  constructor(value) {
4    this.value = value;
5    this.left = null;
6    this.right = null;
7  }
8}
9
10class BinarySearchTree {
11  constructor() {
12    this.root = null;
13  }
14
15  insert(value) {
16    const newNode = new Node(value);
17    if (this.root === null) {
18      this.root = newNode;
19      return this;
20    }
21    let current = this.root;
22    while (true) {
23      if (value === current.value) return undefined;
24      if (value < current.value) {
25        if (current.left === null) {
26          current.left = newNode;
27          return this;
28        }
29        current = current.left;
30      } else {
31        if (current.right === null) {
32          current.right = newNode;
33          return this;
34        }
35        current = current.right;
36      }
37    }
38  }
39
40  search(value, node = this.root) {
41    if (node === null || node.value === value)
42      return node;
43    if (value < node.value) return this.search(value, node.left);
44    return this.search(value, node.right);
45  }
46}

Related Lessons

Binary Search Tree

Intuition

Concept

How it Works

Step-by-Step Breakdown

When to Use

When NOT to Use

How to Identify

Sample Problems

Validate BST

Lowest Common Ancestor

Convert Sorted Array to BST

AI resume checker — match your resume to the job description

Stack

Queue

Deque

Circular Queue

Frequently Asked Questions

What is the BST invariant?

What is the time complexity of BST operations?

How to handle duplicate values in a BST?