Intro to Binary Trees for Complete Beginners

A binary tree is a way to organize data like a family tree. Each item lives in a node. Each node can point to up to two children: a left child and a right child. In a special kind of binary tree called a Binary Search Tree (BST), small values go left and big values go right. This rule keeps data tidy so we can find, add, and remove items efficiently.

JavaScript Implementation


// A simple Binary Search Tree (BST) in JavaScript (OOP style)

class TreeNode {
  constructor(value) {
    this.value = value;
    this.left = null;
    this.right = null;
  }
}

class BinarySearchTree {
  constructor() {
    this.root = null;
    this._size = 0;
  }

  // Insert a value (ignores duplicates for simplicity)
  insert(value) {
    const node = new TreeNode(value);
    if (!this.root) {
      this.root = node;
      this._size++;
      return this;
    }
    let current = this.root;
    while (true) {
      if (value === current.value) return this; // ignore duplicates
      if (value < current.value) {
        if (!current.left) { current.left = node; this._size++; return this; }
        current = current.left;
      } else {
        if (!current.right) { current.right = node; this._size++; return this; }
        current = current.right;
      }
    }
  }

  // Does the value exist?
  contains(value) {
    let current = this.root;
    while (current) {
      if (value === current.value) return true;
      current = value < current.value ? current.left : current.right;
    }
    return false;
  }

  // Smallest value in the whole tree (or a subtree)
  min(node = this.root) {
    if (!node) return null;
    while (node.left) node = node.left;
    return node.value;
  }

  // Largest value
  max(node = this.root) {
    if (!node) return null;
    while (node.right) node = node.right;
    return node.value;
  }

  // Remove a value
  remove(value) {
    const removeNode = (node, val) => {
      if (!node) return null;
      if (val < node.value) {
        node.left = removeNode(node.left, val);
        return node;
      } else if (val > node.value) {
        node.right = removeNode(node.right, val);
        return node;
      } else {
        // 1) no child
        if (!node.left && !node.right) { this._size--; return null; }
        // 2) one child
        if (!node.left) { this._size--; return node.right; }
        if (!node.right) { this._size--; return node.left; }
        // 3) two children: replace with inorder successor
        const successorValue = this.min(node.right);
        node.value = successorValue;
        node.right = removeNode(node.right, successorValue);
        return node;
      }
    };
    const before = this._size;
    this.root = removeNode(this.root, value);
    if (this._size < before) return true;
    return false;
  }

  // Depth-first traversals
  inorder(visit)   { this._inorder(this.root, visit); }
  preorder(visit)  { this._preorder(this.root, visit); }
  postorder(visit) { this._postorder(this.root, visit); }

  _inorder(node, visit) {
    if (!node) return;
    this._inorder(node.left, visit);
    visit(node.value);
    this._inorder(node.right, visit);
  }
  _preorder(node, visit) {
    if (!node) return;
    visit(node.value);
    this._preorder(node.left, visit);
    this._preorder(node.right, visit);
  }
  _postorder(node, visit) {
    if (!node) return;
    this._postorder(node.left, visit);
    this._postorder(node.right, visit);
    visit(node.value);
  }

  // Breadth-first traversal (level order)
  levelOrder(visit) {
    const q = [];
    if (this.root) q.push(this.root);
    while (q.length) {
      const node = q.shift();
      visit(node.value);
      if (node.left) q.push(node.left);
      if (node.right) q.push(node.right);
    }
  }

  // Height of tree (-1 for empty, 0 for one node)
  height(node = this.root) {
    if (!node) return -1;
    return 1 + Math.max(this.height(node.left), this.height(node.right));
  }

  // Naive balance check (difference in heights no more than 1 at every node)
  isBalanced(node = this.root) {
    if (!node) return true;
    const lh = this.height(node.left);
    const rh = this.height(node.right);
    if (Math.abs(lh - rh) > 1) return false;
    return this.isBalanced(node.left) && this.isBalanced(node.right);
  }

  // Count nodes
  size() { return this._size; }

  // Remove all nodes
  clear() { this.root = null; this._size = 0; }

  // Convenience: get values as array using inorder (sorted)
  toArray() {
    const out = [];
    this.inorder(v => out.push(v));
    return out;
  }
}

// ---- Example usage ----
const bst = new BinarySearchTree();
[8, 3, 10, 1, 6, 14, 4, 7, 13].forEach(n => bst.insert(n));
// Search
console.log("Contains 6?", bst.contains(6));        // true
console.log("Min:", bst.min(), "Max:", bst.max());  // 1, 14
// Traversals
bst.inorder(v => console.log("IN", v));             // 1 3 4 6 7 8 10 13 14
bst.preorder(v => console.log("PRE", v));
bst.postorder(v => console.log("POST", v));
bst.levelOrder(v => console.log("LVL", v));
// Structure info
console.log("Height:", bst.height());               // e.g., 3
console.log("Balanced?", bst.isBalanced());         // true or false
console.log("Size:", bst.size());                   // number of nodes
// Delete examples
bst.remove(6);                                      // remove node with two children
bst.remove(14);                                     // remove leaf or one-child node
console.log("After deletes inorder:", bst.toArray());

Complete Explanation of the Code

TreeNode: a tiny object with a value and two links (left, right) that start as null.
BinarySearchTree: holds root (top node) and _size (node count). Starts empty.
insert(value): if empty, new node becomes root and increases _size. Otherwise, compare and walk left or right until an empty spot is found. Equal values are ignored (duplicate policy).
contains(value): walks from root; go left if the target is smaller, right if larger; return true when matched, false if the search falls off the tree.
min(node) / max(node): keep going left (for min) or right (for max) until no more child; return that value. Works from the whole tree or any subtree.
remove(value): uses a recursive helper to return the updated subtree:
- No children → return null and decrement _size.
- One child → return that child (it replaces the node) and decrement _size.
- Two children → replace the node’s value with the smallest value from its right subtree (inorder successor), then delete that successor from the right.
Traversals:
- inorder (left, node, right) prints sorted values for a BST.
- preorder (node, left, right) is useful for copying structure.
- postorder (left, right, node) is common for cleanup.
- levelOrder uses a queue to visit nodes row by row.
height(node): returns -1 for empty, otherwise 1 + max(height(left), height(right)).
isBalanced(node): checks each node’s left/right heights; if any difference is > 1, the tree is not balanced.
size(), clear(), toArray(): utility helpers to count nodes, reset the tree, and collect sorted values via inorder.
Example usage: builds a demo tree, shows searches, traversals, structure info, and deletions.

Performance Note: The queue in levelOrder uses Array.prototype.shift(), which moves items and can be slower for very large trees. For high-volume workloads, consider a double-ended queue (deque) implementation to achieve O(1) pops from the front.

Standard Pseudocode


// DATA STRUCTURES
RECORD NODE
  value
  left
  right
END RECORD

RECORD BST
  root
  SIZE
END RECORD

// CONSTRUCTION
PROCEDURE INITIALIZE_BST(T)
  SET T.root TO NULL
  SET T.SIZE TO 0
END PROCEDURE

FUNCTION NEW_NODE(V)
  INITIALIZE N AS NODE
  SET N.value TO V
  SET N.left TO NULL
  SET N.right TO NULL
  RETURN N
END FUNCTION

// INSERT (duplicates ignored)
PROCEDURE INSERT(T, V)
  IF T.root IS NULL THEN
    SET T.root TO CALL NEW_NODE(V)
    INCREMENT T.SIZE
    RETURN
  END IF

  SET CURRENT TO T.root
  WHILE TRUE DO
    IF V = CURRENT.value THEN
      // duplicate: do nothing (policy)
      RETURN
    END IF

    IF V < CURRENT.value THEN
      IF CURRENT.left IS NULL THEN
        SET CURRENT.left TO CALL NEW_NODE(V)
        INCREMENT T.SIZE
        RETURN
      ELSE
        SET CURRENT TO CURRENT.left
      END IF
    ELSE
      IF CURRENT.right IS NULL THEN
        SET CURRENT.right TO CALL NEW_NODE(V)
        INCREMENT T.SIZE
        RETURN
      ELSE
        SET CURRENT TO CURRENT.right
      END IF
    END IF
  END WHILE
END PROCEDURE

// SEARCH (contains)
FUNCTION CONTAINS(T, V)
  SET CURRENT TO T.root
  WHILE CURRENT IS NOT NULL DO
    IF V = CURRENT.value THEN
      RETURN TRUE
    END IF

    IF V < CURRENT.value THEN
      SET CURRENT TO CURRENT.left
    ELSE
      SET CURRENT TO CURRENT.right
    END IF
  END WHILE
  RETURN FALSE
END FUNCTION

// MIN / MAX
FUNCTION MIN_VALUE(T, START_NODE OPTIONAL)
  IF START_NODE IS NOT PROVIDED THEN
    SET NODE TO T.root
  ELSE
    SET NODE TO START_NODE
  END IF

  IF NODE IS NULL THEN
    RETURN NULL
  END IF

  WHILE NODE.left IS NOT NULL DO
    SET NODE TO NODE.left
  END WHILE
  RETURN NODE.value
END FUNCTION

FUNCTION MAX_VALUE(T, START_NODE OPTIONAL)
  IF START_NODE IS NOT PROVIDED THEN
    SET NODE TO T.root
  ELSE
    SET NODE TO START_NODE
  END IF

  IF NODE IS NULL THEN
    RETURN NULL
  END IF

  WHILE NODE.right IS NOT NULL DO
    SET NODE TO NODE.right
  END WHILE
  RETURN NODE.value
END FUNCTION

// REMOVE (returns whether a node was removed)
FUNCTION REMOVE(T, V)
  SET REMOVED_BEFORE TO T.SIZE

  FUNCTION REMOVE_NODE(N, X)
    IF N IS NULL THEN
      RETURN NULL
    END IF

    IF X < N.value THEN
      SET N.left TO CALL REMOVE_NODE(N.left, X)
      RETURN N
    ELSE IF X > N.value THEN
      SET N.right TO CALL REMOVE_NODE(N.right, X)
      RETURN N
    ELSE
      // CASE: NO CHILD
      IF N.left IS NULL AND N.right IS NULL THEN
        DECREMENT T.SIZE
        RETURN NULL
      END IF

      // CASE: ONE CHILD
      IF N.left IS NULL THEN
        DECREMENT T.SIZE
        RETURN N.right
      END IF
      IF N.right IS NULL THEN
        DECREMENT T.SIZE
        RETURN N.left
      END IF

      // CASE: TWO CHILDREN - replace with inorder successor (smallest in right subtree)
      SET SUCCESSOR_VALUE TO CALL MIN_VALUE(T, N.right)
      SET N.value TO SUCCESSOR_VALUE
      SET N.right TO CALL REMOVE_NODE(N.right, SUCCESSOR_VALUE)
      RETURN N
    END IF
  END FUNCTION

  SET T.root TO CALL REMOVE_NODE(T.root, V)
  IF T.SIZE < REMOVED_BEFORE THEN
    RETURN TRUE
  ELSE
    RETURN FALSE
  END IF
END FUNCTION

// TRAVERSALS (Depth-First)
PROCEDURE INORDER(NODE, VISIT)
  IF NODE IS NULL THEN RETURN END IF
  CALL INORDER(NODE.left, VISIT)
  CALL VISIT(NODE.value)
  CALL INORDER(NODE.right, VISIT)
END PROCEDURE

PROCEDURE PREORDER(NODE, VISIT)
  IF NODE IS NULL THEN RETURN END IF
  CALL VISIT(NODE.value)
  CALL PREORDER(NODE.left, VISIT)
  CALL PREORDER(NODE.right, VISIT)
END PROCEDURE

PROCEDURE POSTORDER(NODE, VISIT)
  IF NODE IS NULL THEN RETURN END IF
  CALL POSTORDER(NODE.left, VISIT)
  CALL POSTORDER(NODE.right, VISIT)
  CALL VISIT(NODE.value)
END PROCEDURE

// TRAVERSAL (Breadth-First / Level Order)
PROCEDURE LEVEL_ORDER(T, VISIT)
  INITIALIZE Q AS EMPTY QUEUE
  IF T.root IS NOT NULL THEN
    ENQUEUE T.root INTO Q
  END IF

  WHILE Q IS NOT EMPTY DO
    SET N TO DEQUEUE FROM Q
    CALL VISIT(N.value)
    IF N.left IS NOT NULL THEN ENQUEUE N.left INTO Q END IF
    IF N.right IS NOT NULL THEN ENQUEUE N.right INTO Q END IF
  END WHILE
END PROCEDURE

// HEIGHT (-1 for empty, 0 for single node)
FUNCTION HEIGHT(NODE)
  IF NODE IS NULL THEN
    RETURN -1
  END IF
  RETURN 1 + MAX(CALL HEIGHT(NODE.left), CALL HEIGHT(NODE.right))
END FUNCTION

// BALANCE CHECK (naive)
FUNCTION IS_BALANCED(NODE)
  IF NODE IS NULL THEN
    RETURN TRUE
  END IF
  SET LH TO CALL HEIGHT(NODE.left)
  SET RH TO CALL HEIGHT(NODE.right)
  IF ABS(LH - RH) > 1 THEN
    RETURN FALSE
  END IF
  RETURN CALL IS_BALANCED(NODE.left) AND CALL IS_BALANCED(NODE.right)
END FUNCTION

// SIZE, CLEAR, TO_ARRAY
FUNCTION SIZE(T)
  RETURN T.SIZE
END FUNCTION

PROCEDURE CLEAR(T)
  SET T.root TO NULL
  SET T.SIZE TO 0
END PROCEDURE

FUNCTION TO_ARRAY(T)
  INITIALIZE OUT AS EMPTY LIST
  PROCEDURE PUSH_VALUE(V)
    APPEND V TO OUT
  END PROCEDURE
  CALL INORDER(T.root, PUSH_VALUE)
  RETURN OUT
END FUNCTION

Explanation of the Pseudocode

NODE stores one value and up to two child links (left, right); BST stores the whole tree plus a SIZE counter.
INSERT follows the “smaller-left / larger-right” rule until an empty spot is found; duplicates stop immediately (ignored).
CONTAINS walks the tree comparing as it goes; it succeeds if a match is found, otherwise returns FALSE when it reaches empty.
MIN_VALUE and MAX_VALUE repeatedly move left or right to find the smallest or largest value; starting node can be the root or any subtree.
REMOVE handles: leaf (delete), one child (promote child), or two children (copy inorder successor value from right subtree, then delete that successor).
Traversals: INORDER yields sorted results on a BST; PREORDER lists parents before children; POSTORDER lists children before parents; LEVEL_ORDER visits by rows using a queue.
HEIGHT gives -1 for empty and otherwise counts the longest path by combining child heights; IS_BALANCED checks that left/right heights never differ by more than one.
SIZE, CLEAR, TO_ARRAY provide counting, resetting, and a sorted list of values via INORDER.