A+DS

Binary Search Tree

A tree where left is smaller, right is bigger.

A Binary Search Tree organizes values so that for every node, all values in the left subtree are smaller and all in the right are larger. This makes searching, inserting, and deleting efficient by eliminating half the tree at each step.

         [ 50 ]
        /       \
     [30]       [70]
    /    \     /    \
  [20]  [40] [60]  [80]

  Insert 35: 50→30→40→left = [35]
  Always: left < parent < right

How it works

  1. 1Compare the value with the current node
  2. 2If smaller, go left; if larger, go right
  3. 3For insert: place at the empty spot you reach
  4. 4For delete: handle 3 cases (leaf, one child, two children)

Loading...