<style> .reveal-up, .reveal-left, .reveal-right, .reveal-stagger > * { opacity: 1 !important; transform: none !important; } </style>
  1. Learn
  2. DSA
  3. Trees
All lessons in this course

Foundations

Linear data structures

Searching and sorting

Hashing and problem-solving techniques

Trees

Graphs

Algorithm design

Master level

Lesson 27 of 50 15 minIntermediate

Binary search trees

Keep keys in order inside a tree so that search, insert and delete follow one path from the root, handle the three delete cases, see how sorted input breaks it, and use SortedSet and SortedDictionary.

A sorted array gives fast binary search but slow inserts (everything after the new item must shift). A linked list gives fast inserts but slow search. A binary search tree (BST) aims for both: O(log n) search and O(log n) insert, as long as it stays balanced.

The BST rule

For every node: all keys in its left subtree are smaller, all keys in its right subtree are bigger. Searching is then binary search on a tree: compare with the node, go left if smaller, right if bigger. Each comparison throws away a whole subtree.

Interactive

Binary search tree lab

Every key in a node’s left subtree is smaller, every key in its right subtree is bigger. So each comparison sends you one way only.

Start from
203540306560807050
Keys 9 · Height 3 · Best possible height for 9 keys 3 · Comparisons 0
Type a key and press Search, Insert or Delete. Try “Sorted order” to see what goes wrong.
Bst.cs
var bst = new Bst();foreach (int x in new[] { 50, 30, 70, 20, 40, 60, 80 }) bst.Insert(x); Console.WriteLine(bst.Contains(60));Console.WriteLine(bst.Contains(65));Console.WriteLine(string.Join(" ", bst.InOrder())); class Bst{    private class Node    {        public int Key;        public Node? Left, Right;        public Node(int key) => Key = key;    }    private Node? _root;     public void Insert(int key) => _root = Insert(_root, key);     private static Node Insert(Node? n, int key)    {        if (n is null) return new Node(key);          // fell off the tree: attach here        if (key < n.Key) n.Left = Insert(n.Left, key);        else if (key > n.Key) n.Right = Insert(n.Right, key);        return n;                                     // equal: already present    }     public bool Contains(int key)    {        var n = _root;        while (n is not null)        {            if (key == n.Key) return true;            n = key < n.Key ? n.Left : n.Right;       // one way only        }        return false;    }     public List<int> InOrder()    {        var result = new List<int>();        Walk(_root, result);        return result;    }     private static void Walk(Node? n, List<int> result)    {        if (n is null) return;        Walk(n.Left, result);        result.Add(n.Key);        Walk(n.Right, result);    }}
Output
True
False
20 30 40 50 60 70 80

The smallest key is found by going left until you cannot; the largest by going right. In-order traversal lists every key in sorted order, for free.

Deleting: three cases

  1. A leaf: just remove it.
  2. One child: the child takes the deleted node’s place.
  3. Two children: find the in-order successor, the smallest key in the right subtree. Copy its key into this node, then delete the successor from the right subtree. The successor has no left child, so that second delete is case 1 or 2.
BstRemove.cs
// inside the Bst classpublic void Remove(int key) => _root = Remove(_root, key); private static Node? Remove(Node? n, int key){    if (n is null) return null;                       // not found    if (key < n.Key) n.Left = Remove(n.Left, key);    else if (key > n.Key) n.Right = Remove(n.Right, key);    else    {        if (n.Left is null) return n.Right;           // leaf or one child        if (n.Right is null) return n.Left;         var s = n.Right;                              // two children:        while (s.Left is not null) s = s.Left;        // smallest key on the right        n.Key = s.Key;                                // copy the successor up…        n.Right = Remove(n.Right, s.Key);             // …and delete it below    }    return n;}

The catch: insertion order decides the shape

Insert 10, 20, 30, 40, 50 in that order and every new key is bigger than all before it, so it always goes right. The “tree” is a chain of height n − 1, and every operation is O(n), no better than a linked list. Sorted or nearly sorted input (IDs, dates, timestamps) is very common in practice. Try “Sorted order” in the widget.

OperationBalanced BSTDegenerate BST
Search, insert, deleteO(log n)O(n)
Min / maxO(log n)O(n)
All keys in orderO(n)O(n)

The fix is a self-balancing tree that reshapes itself after inserts and deletes (next lesson). Unless you are learning or have a special need, never write your own BST for production. Use the balanced ones .NET provides.

BSTs in .NET: SortedSet and SortedDictionary

SortedSet<T> and SortedDictionary<TKey, TValue> are red-black trees: balanced BSTs with guaranteed O(log n) operations. Unlike HashSet and Dictionary, they keep keys in order, so you can ask for the minimum, the maximum or everything in a range.

SortedCollections.cs
var levels = new SortedSet<double> { 12.0, 0.0, 4.0, 8.0, 16.0 };Console.WriteLine(levels.Min + " " + levels.Max);Console.WriteLine(string.Join(" ", levels.GetViewBetween(4.0, 12.0)));   // a range, inclusive var beams = new SortedDictionary<string, double>{    ["B-20"] = 6.0,    ["B-03"] = 4.5,    ["B-11"] = 7.2};foreach (var (id, length) in beams)          // always in key order    Console.WriteLine($"{id}: {length}");
Output
0 16
4 8 12
B-03: 4.5
B-11: 7.2
B-20: 6
NeedUse
Fast lookup by key, order does not matterDictionary / HashSet: O(1)
Keys kept sorted, min/max, rangesSortedDictionary / SortedSet: O(log n)
Sorted, built once, then mostly readSortedList or a sorted array + binary search (less memory)
Quick check

You insert 5, 3, 8, 1, 4 into an empty BST. What is the parent of 4?

Quick check

You delete a node with two children. Which key replaces it?

Practice

Write IsBst(Node? n) that checks whether a binary tree follows the BST rule. Careful: checking only each node against its own children is not enough. In 50 → left 30 → right 60, 60 is bigger than its parent 30, but it sits in the left subtree of 50, so the tree is not a BST.

Show a hint

Pass down the range a key is allowed to be in. Going left, the current key becomes the upper bound; going right, it becomes the lower bound. Use long bounds so int.MinValue and int.MaxValue keys still work.

Show the solution
Solution.cs
var good = new Node(50, new Node(30, new Node(20), new Node(40)), new Node(70));var bad = new Node(50, new Node(30, new Node(20), new Node(60)), new Node(70)); Console.WriteLine(IsBst(good));Console.WriteLine(IsBst(bad)); static bool IsBst(Node? n, long min = long.MinValue, long max = long.MaxValue){    if (n is null) return true;    if (n.Key <= min || n.Key >= max) return false;          // outside its allowed range    return IsBst(n.Left, min, n.Key) && IsBst(n.Right, n.Key, max);} record Node(int Key, Node? Left = null, Node? Right = null);
Output
True
False

Remember

  • BST rule: left subtree smaller, right subtree bigger, at every node.
  • Search, insert and delete follow one root-to-leaf path: O(height).
  • Delete has three cases; with two children, swap in the in-order successor.
  • Sorted input makes a plain BST degenerate (O(n)). Use SortedSet / SortedDictionary, which are balanced red-black trees.
0 of 50 lessons completed