Binary Tree Data Structure: Complete Guide with Code Examples

A binary tree is a hierarchical data structure where each node has at most two children — called the left child and the right child. Binary trees underpin database indexes, file systems, compilers, and nearly every efficient search algorithm. They appear in roughly 25–30% of coding interview questions at major tech companies.

Quick reference

Worst case for a plain BST occurs when the tree degenerates into a linked list (all insertions in sorted order).

Tree terminology

Types of binary trees

Full binary tree

Every node has 0 or 2 children — never just one.

Complete binary tree

All levels are fully filled except possibly the last, which is filled from left to right.
→ Used in binary heaps.

Perfect binary tree

All internal nodes have exactly 2 children and all leaves are at the same level.
A perfect tree with height h has 2^(h+1) − 1 nodes.

Degenerate (skewed) tree

Every node has only one child — essentially a linked list.
This is the worst case for a plain BST.

Balanced binary tree

Height is kept at O(log n) by a balancing rule.
Examples: AVL trees, Red-Black trees (used in Java TreeMap, C++ std::map).

Node structure

# Python
class TreeNode:
    def __init__(self, val=0):
        self.val = val
        self.left = None
        self.right = None

// JavaScript
class TreeNode {
  constructor(val = 0) {
    this.val = val;
    this.left = null;
    this.right = null;
  }
}

// Java
class TreeNode {
    int val;
    TreeNode left, right;
    TreeNode(int val) { this.val = val; }
}

// Go
type TreeNode struct {
    Val   int
    Left  *TreeNode
    Right *TreeNode
}

Binary Search Tree (BST)

A BST adds one invariant to the binary tree structure:

For every node N: all values in the left subtree < N.val < all values in the right subtree.

This invariant makes search, insert, and delete all O(log n) on average.

Insert

def insert(root, val):
    if root is None:
        return TreeNode(val)
    if val < root.val:
        root.left = insert(root.left, val)
    elif val > root.val:
        root.right = insert(root.right, val)
    return root

function insert(root, val) {
  if (!root) return new TreeNode(val);
  if (val < root.val) root.left = insert(root.left, val);
  else if (val > root.val) root.right = insert(root.right, val);
  return root;
}

Search

def search(root, val):
    if root is None or root.val == val:
        return root
    if val < root.val:
        return search(root.left, val)
    return search(root.right, val)

Delete

Deletion has three cases:

1. Leaf node — simply remove it.
2. One child — replace the node with its child.
3. Two children — replace the node's value with its in-order successor (smallest value in the right subtree), then delete the successor.

def delete(root, val):
    if root is None:
        return None
    if val < root.val:
        root.left = delete(root.left, val)
    elif val > root.val:
        root.right = delete(root.right, val)
    else:
        # Case 1 & 2
        if root.left is None:
            return root.right
        if root.right is None:
            return root.left
        # Case 3: find in-order successor
        successor = root.right
        while successor.left:
            successor = successor.left
        root.val = successor.val
        root.right = delete(root.right, successor.val)
    return root

Tree traversals

Traversal order determines the sequence in which nodes are visited. There are four classic traversals.

Inorder (Left → Root → Right)

Visits nodes in ascending order for a BST.

def inorder(root, result=[]):
    if root:
        inorder(root.left, result)
        result.append(root.val)
        inorder(root.right, result)
    return result

function inorder(root, result = []) {
  if (root) {
    inorder(root.left, result);
    result.push(root.val);
    inorder(root.right, result);
  }
  return result;
}

Preorder (Root → Left → Right)

Useful for copying or serializing a tree.

def preorder(root, result=[]):
    if root:
        result.append(root.val)
        preorder(root.left, result)
        preorder(root.right, result)
    return result

Postorder (Left → Right → Root)

Useful for deleting a tree or evaluating expression trees (children before parent).

def postorder(root, result=[]):
    if root:
        postorder(root.left, result)
        postorder(root.right, result)
        result.append(root.val)
    return result

Level-order / BFS (Breadth-First)

Visits nodes level by level using a queue. Essential for finding shortest paths and many interview problems.

from collections import deque

def level_order(root):
    if not root:
        return []
    result, queue = [], deque([root])
    while queue:
        level_size = len(queue)
        level = []
        for _ in range(level_size):
            node = queue.popleft()
            level.append(node.val)
            if node.left:
                queue.append(node.left)
            if node.right:
                queue.append(node.right)
        result.append(level)
    return result

function levelOrder(root) {
  if (!root) return [];
  const result = [], queue = [root];
  while (queue.length) {
    const levelSize = queue.length;
    const level = [];
    for (let i = 0; i < levelSize; i++) {
      const node = queue.shift();
      level.push(node.val);
      if (node.left) queue.push(node.left);
      if (node.right) queue.push(node.right);
    }
    result.push(level);
  }
  return result;
}

public List<List<Integer>> levelOrder(TreeNode root) {
    List<List<Integer>> result = new ArrayList<>();
    if (root == null) return result;
    Queue<TreeNode> queue = new LinkedList<>();
    queue.offer(root);
    while (!queue.isEmpty()) {
        int size = queue.size();
        List<Integer> level = new ArrayList<>();
        for (int i = 0; i < size; i++) {
            TreeNode node = queue.poll();
            level.add(node.val);
            if (node.left != null) queue.offer(node.left);
            if (node.right != null) queue.offer(node.right);
        }
        result.add(level);
    }
    return result;
}

func levelOrder(root *TreeNode) [][]int {
    if root == nil { return nil }
    result := [][]int{}
    queue := []*TreeNode{root}
    for len(queue) > 0 {
        size := len(queue)
        level := []int{}
        for i := 0; i < size; i++ {
            node := queue[0]
            queue = queue[1:]
            level = append(level, node.Val)
            if node.Left != nil { queue = append(queue, node.Left) }
            if node.Right != nil { queue = append(queue, node.Right) }
        }
        result = append(result, level)
    }
    return result
}

Traversal comparison

Iterative traversals (stack-based)

Recursion uses the call stack implicitly. You can replicate this with an explicit stack.

Iterative inorder

def inorder_iterative(root):
    result, stack = [], []
    current = root
    while current or stack:
        while current:
            stack.append(current)
            current = current.left
        current = stack.pop()
        result.append(current.val)
        current = current.right
    return result

Height and depth

def height(root):
    if root is None:
        return -1  # use 0 if counting nodes instead of edges
    return 1 + max(height(root.left), height(root.right))

def depth(root, target, d=0):
    if root is None:
        return -1
    if root.val == target:
        return d
    left = depth(root.left, target, d + 1)
    return left if left != -1 else depth(root.right, target, d + 1)

AVL tree (balanced BST)

An AVL tree is a self-balancing BST where for every node, the height difference between left and right subtrees (the balance factor) is at most 1.

Balance factor = height(left subtree) − height(right subtree)
Valid values: −1, 0, 1

When an insertion or deletion violates this, the tree performs rotations to restore balance.

AVL trees guarantee O(log n) for all operations. They are used in databases and file systems where lookups dominate.

Binary heap

A binary heap is a complete binary tree that satisfies the heap property:

• Min-heap: every parent ≤ its children (root is the minimum)
• Max-heap: every parent ≥ its children (root is the maximum)

Heaps are commonly stored in an array (no pointers needed):

For node at index i:
  Left child  → 2i + 1
  Right child → 2i + 2
  Parent      → (i − 1) // 2

Used in: priority queues, Dijkstra's algorithm, heap sort.

Common interview problems

1. Maximum depth of a binary tree

def max_depth(root):
    if root is None:
        return 0
    return 1 + max(max_depth(root.left), max_depth(root.right))

Time: O(n) | Space: O(h) where h is the height.

2. Check if a binary tree is balanced

A tree is balanced if for every node, |height(left) − height(right)| ≤ 1.

def is_balanced(root):
    def check(node):
        if node is None:
            return 0
        left = check(node.left)
        right = check(node.right)
        if left == -1 or right == -1 or abs(left - right) > 1:
            return -1
        return 1 + max(left, right)
    return check(root) != -1

3. Lowest Common Ancestor (LCA)

def lca(root, p, q):
    if root is None or root == p or root == q:
        return root
    left = lca(root.left, p, q)
    right = lca(root.right, p, q)
    if left and right:
        return root  # p and q are in different subtrees
    return left or right

LCA in a BST (exploits BST property):

def lca_bst(root, p, q):
    while root:
        if p.val < root.val and q.val < root.val:
            root = root.left
        elif p.val > root.val and q.val > root.val:
            root = root.right
        else:
            return root

4. Diameter of a binary tree

The diameter is the longest path between any two nodes (may not pass through the root).

def diameter(root):
    max_d = [0]
    def depth(node):
        if node is None:
            return 0
        left, right = depth(node.left), depth(node.right)
        max_d[0] = max(max_d[0], left + right)
        return 1 + max(left, right)
    depth(root)
    return max_d[0]

5. Validate a Binary Search Tree

def is_valid_bst(root, low=float('-inf'), high=float('inf')):
    if root is None:
        return True
    if root.val <= low or root.val >= high:
        return False
    return (is_valid_bst(root.left, low, root.val) and
            is_valid_bst(root.right, root.val, high))

6. Serialize and deserialize a binary tree

def serialize(root):
    """Preorder serialization."""
    if root is None:
        return 'N'
    return f"{root.val},{serialize(root.left)},{serialize(root.right)}"

def deserialize(data):
    vals = iter(data.split(','))
    def build():
        val = next(vals)
        if val == 'N':
            return None
        node = TreeNode(int(val))
        node.left = build()
        node.right = build()
        return node
    return build()

7. Right side view of a binary tree

Return the value of the rightmost node at each level.

from collections import deque

def right_side_view(root):
    if not root:
        return []
    result, queue = [], deque([root])
    while queue:
        for i in range(len(queue)):
            node = queue.popleft()
            if i == len(queue):   # last node in level
                result.append(node.val)
            if node.left:
                queue.append(node.left)
            if node.right:
                queue.append(node.right)
    return result

8. Kth smallest element in a BST

Inorder traversal yields sorted order — take the kth element.

def kth_smallest(root, k):
    stack, current = [], root
    while True:
        while current:
            stack.append(current)
            current = current.left
        current = stack.pop()
        k -= 1
        if k == 0:
            return current.val
        current = current.right

Interview problems cheat sheet

Binary tree vs other data structures

When to use a binary tree

Use a BST / balanced BST when:

• You need data sorted and need fast lookups, insertions, and deletions.
• You need range queries ("find all values between 10 and 50").
• You need in-order iteration over sorted elements.

Use a heap when:

• You only care about the minimum or maximum element.
• You need a priority queue.

Use a hash table instead when:

• You need O(1) average lookups and don't care about ordering.

Common mistakes

FAQ

What is the difference between a binary tree and a binary search tree?
A binary tree is any tree where nodes have at most two children. A BST adds the ordering invariant: left < node < right. All BSTs are binary trees, but not all binary trees are BSTs.

What is the time complexity of tree traversal?
All four traversals (inorder, preorder, postorder, level-order) visit every node exactly once: O(n) time and O(h) space where h is the height (O(n) worst case for a skewed tree, O(log n) for a balanced tree).

When should I use DFS vs BFS on a tree?
Use DFS (recursive or iterative with stack) for problems involving depth, paths, subtrees, or when memory is a concern on wide trees. Use BFS (queue) for level-by-level processing, finding shortest paths, or when the answer is likely near the root.

What is the difference between height and depth?
Height is measured from a node downward to its deepest leaf. Depth is measured from the root down to a node. The height of the tree = height of the root = depth of the deepest leaf.

Is a balanced binary tree the same as an AVL tree?
No. An AVL tree is a specific implementation of a balanced BST. A "balanced binary tree" is a general concept. Red-Black trees and B-trees are also balanced, but with different balancing rules than AVL.

Why is O(n) insert possible in a BST?
If you insert elements in sorted order (1, 2, 3, 4, …), every new node goes to the right, creating a chain — a degenerate BST identical to a linked list. This makes all operations O(n). Use an AVL or Red-Black tree to prevent this.