A binary search tree (BST) is a binary tree arranged so that searching is fast. It combines the quick lookups of binary search with the easy insertion of a linked structure. This lesson explains the rule, then shows insertion and search.

The BST property

For every node:

  • All values in its left subtree are less than the node’s value.
  • All values in its right subtree are greater than the node’s value.

(Duplicates are either disallowed or placed consistently on one side.)

Building a BST from 8, 3, 10, 1, 6, 14 gives:

        8
      /   
     3     10
    /       
   1   6      14

Search

Start at the root and compare the target with the current node:

  • Equal: found.
  • Smaller: go left.
  • Larger: go right.
  • Reach null: the value is not in the tree.
FUNCTION search(node, target)
   if node = null then
      return false
   else if target = node.data then
      return true
   else if target < node.data then
      return search(node.left, target)
   else
      return search(node.right, target)
   end if
END FUNCTION

To find 6: 6 < 8, go left to 3; 6 > 3, go right to 6; found. Only three nodes were checked rather than all six.

Insert

New values are always added as leaves. Search for where the value would be, and attach it at the empty spot.

FUNCTION insert(node, value)
   if node = null then
      return new Node(value)
   end if
   if value < node.data then
      node.left = insert(node.left, value)
   else if value > node.data then
      node.right = insert(node.right, value)
   end if
   return node
END FUNCTION

Inserting 7: 7 < 8, left to 3; 7 > 3, right to 6; 7 > 6, right child of 6 is empty, so 7 becomes the right child of 6.

Efficiency

Each comparison discards one whole subtree. If the tree is balanced (roughly equal heights on both sides), search and insert take O(log n) steps. With a million items, that is around 20 comparisons.

However, inserting values that are already in order (1, 2, 3, 4, 5) produces a degenerate tree that is just a line. Then the height is n and operations become O(n). Self-balancing trees such as AVL and red-black trees avoid this by rebalancing after changes.

Related operations

  • In-order traversal outputs the values in sorted order.
  • Minimum is the leftmost node; maximum is the rightmost.
  • Delete has three cases: a leaf (remove it), a node with one child (replace the node with the child), and a node with two children (replace its value with its in-order successor, then remove that node).

Check your understanding

In a BST, where do values smaller than a node go?

  • In its left subtree
  • In its right subtree
  • At the root
  • Anywhere

Answer: In its left subtree. Larger values go to the right.

To search for 14 in the example tree, which path is followed?

  • 8, 10, 14
  • 8, 3, 6
  • 8, 3, 1
  • 14 only

Answer: 8, 10, 14. Each time 14 is larger, so go right.

What is the time complexity of search in a balanced BST?

  • O(log n)
  • O(n)
  • O(1)
  • O(n squared)

Answer: O(log n). Each step halves the number of candidates.

Why can inserting sorted data into a BST be a problem?

  • It creates a degenerate tree that behaves like a linked list
  • It deletes values
  • It breaks the BST rule
  • It makes the tree perfect

Answer: It creates a degenerate tree that behaves like a linked list. Operations become O(n).

Previous