Data Structures

Binary Trees

● Intermediate ⏱ 10 min read trees

A binary tree is a hierarchical data structure where each node has at most two children, called the left child and the right child. Trees are the foundation for BSTs, heaps, tries, and many interview problems.

Tree Terminology

Text

        1          ← root (no parent)
       / \
      2   3        ← internal nodes (have children)
     / \    \
    4   5    6     ← leaves (no children)

root       — top node (node 1)
leaf       — node with no children (4, 5, 6)
height     — longest path from root to a leaf = 2
depth      — distance from root to a node (root depth = 0)
level      — all nodes at the same depth
subtree    — a node and all its descendants
full BT    — every node has 0 or 2 children
complete BT — all levels filled except possibly last, filled left-to-right
perfect BT  — all leaves at same depth; n = 2^(h+1) − 1 nodes

TreeNode Class

Python

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

# Build the example tree manually
root = TreeNode(1)
root.left  = TreeNode(2)
root.right = TreeNode(3)
root.left.left  = TreeNode(4)
root.left.right = TreeNode(5)
root.right.right = TreeNode(6)

In-order Traversal (Left → Root → Right)

In-order traversal visits the left subtree, then the current node, then the right subtree. For a BST, this produces a sorted sequence.

Python

# Recursive in-order
def inorder(node):
    if node is None:
        return
    inorder(node.left)
    print(node.val, end=" ")
    inorder(node.right)

inorder(root)   # 4 2 5 1 3 6

# Iterative in-order using explicit stack
def inorder_iterative(root):
    result, stack = [], []
    node = root
    while node or stack:
        while node:
            stack.append(node)
            node = node.left
        node = stack.pop()
        result.append(node.val)
        node = node.right
    return result

print(inorder_iterative(root))  # [4, 2, 5, 1, 3, 6]

Pre-order Traversal (Root → Left → Right)

Pre-order visits the current node before its children. Useful for copying or serialising a tree.

Python

# Recursive pre-order
def preorder(node):
    if node is None:
        return
    print(node.val, end=" ")
    preorder(node.left)
    preorder(node.right)

preorder(root)  # 1 2 4 5 3 6

# Iterative pre-order
def preorder_iterative(root):
    if not root:
        return []
    result, stack = [], [root]
    while stack:
        node = stack.pop()
        result.append(node.val)
        if node.right:
            stack.append(node.right)   # right first so left is popped first
        if node.left:
            stack.append(node.left)
    return result

Post-order Traversal (Left → Right → Root)

Post-order visits children before the current node. Used for deletion (delete children before parent) or evaluating expression trees.

Python

def postorder(node):
    if node is None:
        return
    postorder(node.left)
    postorder(node.right)
    print(node.val, end=" ")

postorder(root)  # 4 5 2 6 3 1

Level-order Traversal (BFS)

Level-order visits all nodes level by level using a queue. It is the tree equivalent of Breadth-First Search.

Python

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

print(level_order(root))
# [[1], [2, 3], [4, 5, 6]]

Height & Size

Python

# Height: longest path from root to any leaf
def height(node):
    if node is None:
        return -1          # empty tree has height -1
    return 1 + max(height(node.left), height(node.right))

print(height(root))   # 2

# Size: total number of nodes
def size(node):
    if node is None:
        return 0
    return 1 + size(node.left) + size(node.right)

print(size(root))     # 6

# Check if balanced (|height_left - height_right| <= 1 for every node)
def is_balanced(node):
    def check(n):
        if n is None:
            return 0
        lh = check(n.left)
        rh = check(n.right)
        if lh == -1 or rh == -1 or abs(lh - rh) > 1:
            return -1
        return 1 + max(lh, rh)
    return check(node) != -1

Complexity Table

Operation	Time	Space	Note
Any traversal	O(n)	O(h)	h = height; O(n) for skewed trees
Level-order	O(n)	O(w)	w = max width (queue size)
Height	O(n)	O(h)	Recurse to every leaf
Size	O(n)	O(h)
Search (general)	O(n)	O(h)	No ordering guarantee in plain BT