Overview

A binary tree is a hierarchical data structure where each node has at most two children, referred to as the left child and the right child. Binary trees are fundamental in computer science and serve as the foundation for many advanced data structures and algorithms.

Each node in a binary tree can have zero, one, or two children. Binary trees are particularly useful for implementing search algorithms, expression parsing, and hierarchical data representation.

Key characteristics:

• Maximum two children - Each node has at most left and right child
• Hierarchical structure - Parent-child relationships
• Recursive definition - Tree is defined in terms of subtrees
• Preorder, inorder, postorder - Three main traversal methods
• Complete and full trees - Special tree variants with specific properties

Binary Tree Properties

Structural Properties

• Maximum nodes at level i: 2^i (0-indexed)
• Maximum nodes in tree of height h: 2^(h+1) - 1
• Minimum nodes in tree of height h: h + 1
• Height of complete binary tree with n nodes: ⌊log₂(n)⌋
• Maximum height: n (for skewed tree)
• Minimum height: ⌊log₂(n)⌋ + 1 (for complete tree)

Relationship Properties

• For any binary tree: Number of leaf nodes = Number of nodes with 2 children + 1
• In a complete binary tree: If there are n nodes, then height = ⌊log₂(n)⌋
• For any binary tree: Number of null links = Number of nodes + 1

Types of Binary Trees

1. Full Binary Tree: Every node has 0 or 2 children
2. Complete Binary Tree: All levels filled except possibly last, with leftmost arrangement
3. Perfect Binary Tree: All internal nodes have 2 children and all leaves at same level
4. Skewed Binary Tree: All nodes have only one child (left or right)

Binary Tree Representation

Array Representation (Complete Binary Tree)

• Root at index 0
• For node at index i:
  • Left child at index 2*i + 1
  • Right child at index 2*i + 2
  • Parent at index ⌊(i-1)/2⌋

Linked List Representation

class TreeNode<T> {
  val: T;
  left: TreeNode<T> | null = null;
  right: TreeNode<T> | null = null;
  constructor(val: T) {
    this.val = val;
  }
}

Advantages of linked list:

• Dynamic size
• No memory waste for sparse trees
• Easy to implement tree operations

Disadvantages:

• Extra memory for pointers
• Not cache-friendly like arrays

Binary Tree Traversals

1. Preorder Traversal (Root → Left → Right)

function preorderTraversal(root: TreeNode | null): number[] {
  const result: number[] = [];

  function traverse(node: TreeNode | null): void {
    if (node === null) return;

    result.push(node.val);
    traverse(node.left);
    traverse(node.right);
  }

  traverse(root);
  return result;
}

2. Inorder Traversal (Left → Root → Right)

function inorderTraversal(root: TreeNode | null): number[] {
  const result: number[] = [];

  function traverse(node: TreeNode | null): void {
    if (node === null) return;

    traverse(node.left);
    result.push(node.val);
    traverse(node.right);
  }

  traverse(root);
  return result;
}

3. Postorder Traversal (Left → Right → Root)

function postorderTraversal(root: TreeNode | null): number[] {
  const result: number[] = [];

  function traverse(node: TreeNode | null): void {
    if (node === null) return;

    traverse(node.left);
    traverse(node.right);
    result.push(node.val);
  }

  traverse(root);
  return result;
}

4. Level-Order Traversal (Breadth-First)

function levelOrderTraversal(root: TreeNode | null): number[] {
  if (root === null) return [];

  const result: number[] = [];
  const queue: TreeNode[] = [root];

  while (queue.length > 0) {
    const node = queue.shift()!;
    result.push(node.val);

    if (node.left) queue.push(node.left);
    if (node.right) queue.push(node.right);
  }

  return result;
}

Binary Tree Operations

1. Insertion

function insertIntoBinaryTree(root: TreeNode | null, val: number): TreeNode | null {
  if (root === null) return new TreeNode(val);

  const queue: TreeNode[] = [root];

  while (queue.length > 0) {
    const node = queue.shift()!;

    if (node.left === null) {
      node.left = new TreeNode(val);
      break;
    } else if (node.right === null) {
      node.right = new TreeNode(val);
      break;
    } else {
      queue.push(node.left);
      queue.push(node.right);
    }
  }

  return root;
}

2. Search

function searchInBinaryTree(root: TreeNode | null, target: number): boolean {
  if (root === null) return false;

  const queue: TreeNode[] = [root];

  while (queue.length > 0) {
    const node = queue.shift()!;

    if (node.val === target) return true;

    if (node.left) queue.push(node.left);
    if (node.right) queue.push(node.right);
  }

  return false;
}

3. Deletion

function deleteFromBinaryTree(root: TreeNode | null, key: number): TreeNode | null {
  if (root === null) return null;

  // If root is the node to delete
  if (root.val === key) {
    // Handle case where node has 0 or 1 child
    if (root.left === null) return root.right;
    if (root.right === null) return root.left;

    // Find inorder successor
    let successor = root.right;
    while (successor.left !== null) {
      successor = successor.left;
    }

    // Replace root value with successor
    root.val = successor.val;

    // Delete successor (which is guaranteed to have 0 or 1 children)
    root.right = deleteFromBinaryTree(root.right, successor.val);
  } else if (key < root.val) {
    root.left = deleteFromBinaryTree(root.left, key);
  } else {
    root.right = deleteFromBinaryTree(root.right, key);
  }

  return root;
}

Binary Tree Applications

1. Expression Trees

Expression trees represent arithmetic expressions where:

• Leaves are operands (numbers)
• Internal nodes are operators (+, -, *, /)

2. Huffman Coding

Huffman trees are used for data compression where:

• More frequent characters have shorter paths
• Less frequent characters have longer paths

3. Decision Trees

Decision trees in machine learning:

• Root node represents decision based on feature
• Internal nodes represent feature tests
• Leaf nodes represent class labels or decisions

4. File System Representation

File systems can be represented as trees:

• Root represents root directory
• Internal nodes represent subdirectories
• Leaf nodes represent files

5. Network Routing

Network routing tables can be represented as trees:

• Root represents network router
• Branches represent network paths
• Leaves represent destination addresses

Time and Space Complexity

Traversal Operations

• Preorder, Inorder, Postorder: O(n) time, O(h) space (h = height)
• Level-order: O(n) time, O(w) space (w = max width)

Search Operations

• Breadth-First Search: O(n) time, O(w) space
• Depth-First Search: O(n) time, O(h) space

Insertion and Deletion

• Average case: O(log n) for balanced trees
• Worst case: O(n) for skewed trees

Note: Performance depends on tree balance. Balanced trees provide better guarantees.

Practice Tips

1. Understand the difference - Know when to use traversal methods
2. Handle edge cases - Empty trees, single nodes, null nodes
3. Use recursion wisely - Leverage recursive structure of trees
4. Choose appropriate representation - Array vs linked list based on use case
5. Practice all traversals - Preorder, inorder, postorder, level-order
6. Know tree properties - Height, width, depth relationships
7. Handle skewed trees - Be aware of worst-case performance