Binary Trees

November 19, 2025

#binary-tree #tree #data-structures #tree-traversal #algorithms #interviewing

Introduction

A binary tree is a hierarchical data structure where each node has at most two children, referred to as the left child and right child. Unlike linear data structures like arrays or linked lists, binary trees organize data in a hierarchical, branching structure that enables efficient searching, sorting, and hierarchical representation.

Binary trees are fundamental to computer science and appear in file systems, databases, compilers, and countless algorithms. By the end of this tutorial, you’ll understand different types of binary trees, how to traverse them, and when to use them.

If you’re new to data structures, review Big-O Notation, Linked Lists, and Queues first.

Binary trees provide hierarchical organization with O(log n) average-case performance for balanced trees, making them ideal for searching, sorting, and representing hierarchical relationships.

What is a binary tree?

A binary tree consists of nodes where each node contains:

Data (or value)
Left child pointer
Right child pointer

Key properties:

The root is the topmost node
Nodes with no children are called leaves (or leaf nodes)
The height of a tree is the longest path from root to leaf
The depth of a node is its distance from the root
Each node can have 0, 1, or 2 children

Types of binary trees

1. Full Binary Tree

Every node has either 0 or 2 children (no node has exactly 1 child).

2. Complete Binary Tree

All levels are completely filled except possibly the last, which is filled from left to right.

3. Perfect Binary Tree

All internal nodes have 2 children, and all leaves are at the same level.

4. Balanced Binary Tree

The height difference between left and right subtrees is at most 1 for every node.

5. Degenerate (Skewed) Tree

Each parent node has only one child (essentially a linked list).

Why use binary trees?

Choose binary trees when:

You need hierarchical data representation (file systems, organization charts)
You need efficient searching in sorted data (Binary Search Trees)
You’re implementing priority queues (heaps)
You need to evaluate expressions (expression trees)
You’re building decision trees or game trees
You need efficient insertion and deletion with ordering

Avoid binary trees when:

You need sequential access (use arrays or linked lists)
You need fast lookup by key without ordering (use hash tables)
You need FIFO/LIFO access (use queues or stacks)

Real-world applications

Binary trees are used extensively:

File systems: Directory structures
Databases: B-trees and B+ trees for indexing
Compilers: Abstract syntax trees (AST) for parsing
Decision making: Decision trees in AI/ML
Routing: Binary trees in network routing algorithms
Game development: Game trees for AI decisions
Huffman coding: Data compression algorithms
Expression evaluation: Mathematical expression trees

Binary tree implementation

Node structure and basic tree

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

class BinaryTree {
  constructor() {
    this.root = null;
  }

  // Helper to create a simple tree for examples
  createSampleTree() {
    this.root = new TreeNode(1);
    this.root.left = new TreeNode(2);
    this.root.right = new TreeNode(3);
    this.root.left.left = new TreeNode(4);
    this.root.left.right = new TreeNode(5);
    return this.root;
  }

  // Get height of tree
  height(node = this.root) {
    if (node === null) return 0;
    const leftHeight = this.height(node.left);
    const rightHeight = this.height(node.right);
    return Math.max(leftHeight, rightHeight) + 1;
  }

  // Count total nodes
  size(node = this.root) {
    if (node === null) return 0;
    return 1 + this.size(node.left) + this.size(node.right);
  }

  // Count leaf nodes
  countLeaves(node = this.root) {
    if (node === null) return 0;
    if (node.left === null && node.right === null) return 1;
    return this.countLeaves(node.left) + this.countLeaves(node.right);
  }
}

// Example usage
const tree = new BinaryTree();
tree.createSampleTree();
console.log("Height:", tree.height());        // 3
console.log("Size:", tree.size());            // 5
console.log("Leaves:", tree.countLeaves());   // 3

class TreeNode:
    def __init__(self, value):
        self.value = value
        self.left = None
        self.right = None

class BinaryTree:
    def __init__(self):
        self.root = None

    def create_sample_tree(self):
        """Helper to create a simple tree for examples"""
        self.root = TreeNode(1)
        self.root.left = TreeNode(2)
        self.root.right = TreeNode(3)
        self.root.left.left = TreeNode(4)
        self.root.left.right = TreeNode(5)
        return self.root

    def height(self, node=None):
        """Get height of tree"""
        if node is None:
            node = self.root
        if node is None:
            return 0
        left_height = self.height(node.left)
        right_height = self.height(node.right)
        return max(left_height, right_height) + 1

    def size(self, node=None):
        """Count total nodes"""
        if node is None:
            node = self.root
        if node is None:
            return 0
        return 1 + self.size(node.left) + self.size(node.right)

    def count_leaves(self, node=None):
        """Count leaf nodes"""
        if node is None:
            node = self.root
        if node is None:
            return 0
        if node.left is None and node.right is None:
            return 1
        return self.count_leaves(node.left) + self.count_leaves(node.right)

# Example usage
tree = BinaryTree()
tree.create_sample_tree()
print("Height:", tree.height())         # 3
print("Size:", tree.size())             # 5
print("Leaves:", tree.count_leaves())   # 3

class TreeNode {
    int value;
    TreeNode left;
    TreeNode right;

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

public class BinaryTree {
    TreeNode root;

    public BinaryTree() {
        this.root = null;
    }

    // Helper to create a simple tree for examples
    public TreeNode createSampleTree() {
        root = new TreeNode(1);
        root.left = new TreeNode(2);
        root.right = new TreeNode(3);
        root.left.left = new TreeNode(4);
        root.left.right = new TreeNode(5);
        return root;
    }

    // Get height of tree
    public int height(TreeNode node) {
        if (node == null) return 0;
        int leftHeight = height(node.left);
        int rightHeight = height(node.right);
        return Math.max(leftHeight, rightHeight) + 1;
    }

    // Count total nodes
    public int size(TreeNode node) {
        if (node == null) return 0;
        return 1 + size(node.left) + size(node.right);
    }

    // Count leaf nodes
    public int countLeaves(TreeNode node) {
        if (node == null) return 0;
        if (node.left == null && node.right == null) return 1;
        return countLeaves(node.left) + countLeaves(node.right);
    }

    public static void main(String[] args) {
        BinaryTree tree = new BinaryTree();
        tree.createSampleTree();
        System.out.println("Height: " + tree.height(tree.root));       // 3
        System.out.println("Size: " + tree.size(tree.root));           // 5
        System.out.println("Leaves: " + tree.countLeaves(tree.root));  // 3
    }
}

Tree traversal methods

Traversal is the process of visiting every node in the tree exactly once in a specific order.

1. In-Order Traversal (Left, Root, Right)

Visit left subtree, then root, then right subtree. For Binary Search Trees, this gives sorted order.

2. Pre-Order Traversal (Root, Left, Right)

Visit root first, then left subtree, then right subtree. Useful for copying trees.

3. Post-Order Traversal (Left, Right, Root)

Visit left subtree, then right subtree, then root. Useful for deleting trees.

4. Level-Order Traversal (Breadth-First)

Visit nodes level by level from left to right. Uses a queue.

Implementation of all traversals

class BinaryTree {
  // ... (previous code)

  // In-Order: Left, Root, Right
  inOrder(node = this.root, result = []) {
    if (node !== null) {
      this.inOrder(node.left, result);
      result.push(node.value);
      this.inOrder(node.right, result);
    }
    return result;
  }

  // Pre-Order: Root, Left, Right
  preOrder(node = this.root, result = []) {
    if (node !== null) {
      result.push(node.value);
      this.preOrder(node.left, result);
      this.preOrder(node.right, result);
    }
    return result;
  }

  // Post-Order: Left, Right, Root
  postOrder(node = this.root, result = []) {
    if (node !== null) {
      this.postOrder(node.left, result);
      this.postOrder(node.right, result);
      result.push(node.value);
    }
    return result;
  }

  // Level-Order: Breadth-First using Queue
  levelOrder() {
    if (this.root === null) return [];

    const result = [];
    const queue = [this.root];

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

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

    return result;
  }
}

// Example usage
const tree = new BinaryTree();
tree.createSampleTree();
console.log("In-Order:", tree.inOrder());       // [4, 2, 5, 1, 3]
console.log("Pre-Order:", tree.preOrder());     // [1, 2, 4, 5, 3]
console.log("Post-Order:", tree.postOrder());   // [4, 5, 2, 3, 1]
console.log("Level-Order:", tree.levelOrder()); // [1, 2, 3, 4, 5]

from collections import deque

class BinaryTree:
    # ... (previous code)

    def in_order(self, node=None, result=None):
        """In-Order: Left, Root, Right"""
        if result is None:
            result = []
        if node is None:
            node = self.root

        if node is not None:
            self.in_order(node.left, result)
            result.append(node.value)
            self.in_order(node.right, result)

        return result

    def pre_order(self, node=None, result=None):
        """Pre-Order: Root, Left, Right"""
        if result is None:
            result = []
        if node is None:
            node = self.root

        if node is not None:
            result.append(node.value)
            self.pre_order(node.left, result)
            self.pre_order(node.right, result)

        return result

    def post_order(self, node=None, result=None):
        """Post-Order: Left, Right, Root"""
        if result is None:
            result = []
        if node is None:
            node = self.root

        if node is not None:
            self.post_order(node.left, result)
            self.post_order(node.right, result)
            result.append(node.value)

        return result

    def level_order(self):
        """Level-Order: Breadth-First using Queue"""
        if self.root is None:
            return []

        result = []
        queue = deque([self.root])

        while queue:
            node = queue.popleft()
            result.append(node.value)

            if node.left:
                queue.append(node.left)
            if node.right:
                queue.append(node.right)

        return result

# Example usage
tree = BinaryTree()
tree.create_sample_tree()
print("In-Order:", tree.in_order())       # [4, 2, 5, 1, 3]
print("Pre-Order:", tree.pre_order())     # [1, 2, 4, 5, 3]
print("Post-Order:", tree.post_order())   # [4, 5, 2, 3, 1]
print("Level-Order:", tree.level_order()) # [1, 2, 3, 4, 5]

import java.util.*;

public class BinaryTree {
    // ... (previous code)

    // In-Order: Left, Root, Right
    public List<Integer> inOrder(TreeNode node, List<Integer> result) {
        if (result == null) result = new ArrayList<>();
        if (node != null) {
            inOrder(node.left, result);
            result.add(node.value);
            inOrder(node.right, result);
        }
        return result;
    }

    // Pre-Order: Root, Left, Right
    public List<Integer> preOrder(TreeNode node, List<Integer> result) {
        if (result == null) result = new ArrayList<>();
        if (node != null) {
            result.add(node.value);
            preOrder(node.left, result);
            preOrder(node.right, result);
        }
        return result;
    }

    // Post-Order: Left, Right, Root
    public List<Integer> postOrder(TreeNode node, List<Integer> result) {
        if (result == null) result = new ArrayList<>();
        if (node != null) {
            postOrder(node.left, result);
            postOrder(node.right, result);
            result.add(node.value);
        }
        return result;
    }

    // Level-Order: Breadth-First using Queue
    public List<Integer> levelOrder() {
        List<Integer> result = new ArrayList<>();
        if (root == null) return result;

        Queue<TreeNode> queue = new LinkedList<>();
        queue.offer(root);

        while (!queue.isEmpty()) {
            TreeNode node = queue.poll();
            result.add(node.value);

            if (node.left != null) queue.offer(node.left);
            if (node.right != null) queue.offer(node.right);
        }

        return result;
    }

    public static void main(String[] args) {
        BinaryTree tree = new BinaryTree();
        tree.createSampleTree();
        System.out.println("In-Order: " + tree.inOrder(tree.root, null));
        // [4, 2, 5, 1, 3]
        System.out.println("Pre-Order: " + tree.preOrder(tree.root, null));
        // [1, 2, 4, 5, 3]
        System.out.println("Post-Order: " + tree.postOrder(tree.root, null));
        // [4, 5, 2, 3, 1]
        System.out.println("Level-Order: " + tree.levelOrder());
        // [1, 2, 3, 4, 5]
    }
}

Common binary tree operations

Finding maximum value

findMax(node = this.root) {
  if (node === null) return -Infinity;

  const leftMax = this.findMax(node.left);
  const rightMax = this.findMax(node.right);

  return Math.max(node.value, leftMax, rightMax);
}

def find_max(self, node=None):
    if node is None:
        node = self.root
    if node is None:
        return float('-inf')

    left_max = self.find_max(node.left)
    right_max = self.find_max(node.right)

    return max(node.value, left_max, right_max)

public int findMax(TreeNode node) {
    if (node == null) return Integer.MIN_VALUE;

    int leftMax = findMax(node.left);
    int rightMax = findMax(node.right);

    return Math.max(node.value, Math.max(leftMax, rightMax));
}

Checking if tree is balanced

isBalanced(node = this.root) {
  if (node === null) return true;

  const leftHeight = this.height(node.left);
  const rightHeight = this.height(node.right);

  const heightDiff = Math.abs(leftHeight - rightHeight);

  return heightDiff <= 1 &&
         this.isBalanced(node.left) &&
         this.isBalanced(node.right);
}

def is_balanced(self, node=None):
    if node is None:
        node = self.root
    if node is None:
        return True

    left_height = self.height(node.left)
    right_height = self.height(node.right)

    height_diff = abs(left_height - right_height)

    return (height_diff <= 1 and
            self.is_balanced(node.left) and
            self.is_balanced(node.right))

public boolean isBalanced(TreeNode node) {
    if (node == null) return true;

    int leftHeight = height(node.left);
    int rightHeight = height(node.right);

    int heightDiff = Math.abs(leftHeight - rightHeight);

    return heightDiff <= 1 &&
           isBalanced(node.left) &&
           isBalanced(node.right);
}

Mirror/Invert a binary tree

mirror(node = this.root) {
  if (node === null) return null;

  // Swap left and right children
  const temp = node.left;
  node.left = node.right;
  node.right = temp;

  // Recursively mirror subtrees
  this.mirror(node.left);
  this.mirror(node.right);

  return node;
}

def mirror(self, node=None):
    if node is None:
        node = self.root
    if node is None:
        return None

    # Swap left and right children
    node.left, node.right = node.right, node.left

    # Recursively mirror subtrees
    self.mirror(node.left)
    self.mirror(node.right)

    return node

public TreeNode mirror(TreeNode node) {
    if (node == null) return null;

    // Swap left and right children
    TreeNode temp = node.left;
    node.left = node.right;
    node.right = temp;

    // Recursively mirror subtrees
    mirror(node.left);
    mirror(node.right);

    return node;
}

Complexity analysis

Operation	Average Case	Worst Case	Notes
Search	O(n)	O(n)	Must check all nodes in general binary tree
Insert	O(n)	O(n)	Finding position requires traversal
Delete	O(n)	O(n)	Finding and removing node
Traversal	O(n)	O(n)	Must visit every node
Height	O(n)	O(n)	Must check all paths
Space	O(n)	O(n)	Storage for n nodes

Note: For balanced binary search trees, search/insert/delete are O(log n).

Common pitfalls

Not handling null nodes: Always check for null before accessing node properties
Stack overflow: Deep recursion on unbalanced trees can cause stack overflow
Modifying during traversal: Be careful when modifying tree structure during traversal
Confusing traversal orders: Know when to use each traversal type
Memory leaks: In manual-memory languages, ensure nodes are properly freed
Off-by-one in height: Remember that a single node has height 1, not 0

When to prefer other data structures

Need O(1) access by index → Use array
Need O(1) key lookup → Use hash table
Need FIFO/LIFO → Use queue/stack
Need guaranteed O(log n) operations → Use balanced BST (AVL, Red-Black)
Need range queries → Use segment tree or Fenwick tree

Practice problems

Find the lowest common ancestor (LCA) of two nodes
Determine if two binary trees are identical
Find the diameter of a binary tree (longest path between any two nodes)
Serialize and deserialize a binary tree
Find all root-to-leaf paths that sum to a given value
Convert a binary tree to its mirror image iteratively
Find the maximum path sum in a binary tree
Check if a binary tree is a subtree of another tree
Print all nodes at distance K from a given node
Construct a binary tree from in-order and pre-order traversals
Find the vertical order traversal of a binary tree
Convert a binary tree to a doubly linked list
Find the boundary traversal of a binary tree
Check if a binary tree is symmetric (mirror of itself)
Find the right view of a binary tree

Complexity summary

Time complexity:
- Traversal: O(n) — visit all nodes
- Search (unbalanced): O(n) — may need to check all nodes
- Height: O(n) — must check all paths
- Most operations: O(n) for general binary trees
Space complexity:
- Storage: O(n) for n nodes
- Recursion stack: O(h) where h is height (O(log n) balanced, O(n) worst case)

Binary trees form the foundation for more advanced tree structures like Binary Search Trees, AVL trees, and heaps. Understanding binary trees deeply will prepare you for these more specialized variants.

Table of Contents