Binary Tree

Binary Search Tree

A binary tree of comparable elements, primarily designed for efficient searching, insertion and deletion.

Each vertex has a (comparable) key and value. Left sub-tree of a vertex has a key less than its parent vertex’s key. Right sub-tree of a vertex has a key greater than its parent vertex’s key.

Insertion

insert(root, key, value):
  if root is null:
    return new Node(key, value)       # base case: empty spot found

  if key < root.key:
    root.left = insert(root.left, key, value)   # go left
  else if key > root.key:
    root.right = insert(root.right, key, value) # go right
  # if key == root.key, duplicate — no-op (or update value)

  return root