Mastering Binary Tree Algorithms: Traversals, LCA, and Serialization

Welcome. Whether you're preparing for coding interviews or deepening your understanding of one of computer science's most fundamental data structures, this guide will walk you through the essential binary tree algorithms. We'll move from foundational traversal patterns to more complex problems like finding the Lowest Common Ancestor and serializing a tree.

A binary tree is a hierarchical structure where each node has at most two children, referred to as the left child and the right child.

# Standard Definition for a binary tree node (Python)
class TreeNode:
    def __init__(self, val=0, left=None, right=None):
        self.val = val
        self.left = left
        self.right = right

---

Part 1: The Core Traversal Patterns (DFS)

Depth-First Search (DFS) explores as far down a branch as possible before backtracking. The magic is in when you process the current node relative to its children. This gives us three classic traversals.

1.1 Preorder Traversal (Root -> Left -> Right)

Policy: "Visit me first, then my entire left subtree, then my entire right subtree."

This is your go-to pattern for creating a copy of a tree or when you need to explore roots before leaves (like in a topological sort of a tree).

Theory Notes to Remember:

• Processing Order: [Node] -> [Left Subtree] -> [Right Subtree]

• Use Case: Serializing a tree, converting a tree to a string.

• Mental Model: You're an explorer who plants a flag at the entrance (root) before exploring the left wing and then the right wing of a building.

Recursive Approach

The recursive solution is elegant and directly mirrors the definition.

def preorder_recursive(root):
    result = []
    def dfs(node):
        if not node:
            return
        # 1. Process Root
        result.append(node.val)
        # 2. Traverse Left
        dfs(node.left)
        # 3. Traverse Right
        dfs(node.right)
    dfs(root)
    return result

LeetCode Example: 144. Binary Tree Preorder Traversal

Iterative Approach

We use a stack to simulate the call stack of recursion. Crucially, we push the right child before the left child so the left child is popped and processed first (LIFO principle).

def preorder_iterative(root):
    if not root:
        return []
    result, stack = [], [root]
    while stack:
        node = stack.pop()
        result.append(node.val)
        # Push right first, so left is processed next - i.m.p.
        if node.right:
            stack.append(node.right)
        if node.left:
            stack.append(node.left)
    return result

---

1.2 Inorder Traversal (Left -> Root -> Right)

Policy: "Visit my entire left subtree first, then me, then my entire right subtree."

For a Binary Search Tree (BST), this processes nodes in non-decreasing order. This is its defining feature.

Theory Notes to Remember:

• Processing Order: [Left Subtree] -> [Node] -> [Right Subtree]

• Use Case: Getting sorted data from a BST.

• Mental Model: You are reading a book. You read the left page, then the center margin, then the right page.

Recursive Approach

def inorder_recursive(root):
    result = []
    def dfs(node):
        if not node:
            return
        # 1. Traverse Left
        dfs(node.left)
        # 2. Process Root
        result.append(node.val)
        # 3. Traverse Right
        dfs(node.right)
    dfs(root)
    return result

LeetCode Example: 94. Binary Tree Inorder Traversal

Iterative Approach

The iterative inorder traversal is trickier. We must go all the way down to the leftmost node first, then backtrack. This is not important but good to have idea.

def inorder_iterative(root):
    result, stack = [], []
    curr = root
    while curr or stack:
        # Step 1: Go as far left as possible
        while curr:
            stack.append(curr)
            curr = curr.left
        # Step 2: Process the node from top of stack
        curr = stack.pop()
        result.append(curr.val)
        # Step 3: Switch to the right subtree
        curr = curr.right
    return result

---

1.3 Postorder Traversal (Left -> Right -> Root)

Policy: "Visit my entire left subtree, then my entire right subtree, and finally me."

This is essential when you need to process children before the parent, such as deleting a tree or evaluating mathematical expressions.

Theory Notes to Remember:

• Processing Order: [Left Subtree] -> [Right Subtree] -> [Node]

• Use Case: Deleting a tree, computing the size of directories.

• Mental Model: An assassin must clear out the left and right wings of a building before the king in the central hall is approached.

Recursive Approach

def postorder_recursive(root):
    result = []
    def dfs(node):
        if not node:
            return
        # 1. Traverse Left
        dfs(node.left)
        # 2. Traverse Right
        dfs(node.right)
        # 3. Process Root
        result.append(node.val)
    dfs(root)
    return result

LeetCode Example: 145. Binary Tree Postorder Traversal

Iterative Approach

The trick here is to think of it as a reversed version of a "Root -> Right -> Left" traversal. We simply do a modified preorder and then reverse the result.

def postorder_iterative(root):
    if not root:
        return []
    result, stack = [], [root]
    while stack:
        node = stack.pop()
        result.append(node.val)
        # Modified Preorder: Left first, then Right
        if node.left:
            stack.append(node.left)
        if node.right:
            stack.append(node.right)
    # Reverse the result to get Left -> Right -> Root
    return result[::-1]

---

Part 2: Breadth-First Search (BFS) / Level-Order Traversal

BFS explores the tree level by level, from top to bottom, left to right. We use a queue (FIFO) data structure.

Policy: "Visit all nodes at the current depth before moving to the next depth."

Theory Notes to Remember:

• Data Structure: Always use a Queue (FIFO).

• Use Case: Finding the shortest path in an unweighted graph/tree, connecting nodes at the same level.

• Mental Model: A ripple spreading outwards in a pond.

LeetCode Example: 102. Binary Tree Level Order Traversal

from collections import deque

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

Key Detail: Tracking level_size is the standard way to group nodes into lists representing each level.

---

Part 3: Lowest Common Ancestor (LCA) of a Binary Tree

The Lowest Common Ancestor (LCA) of two nodes p and q in a binary tree is the deepest node that has both p and q as descendants.

Policy: "Search the tree. If my subtree contains exactly one of the targets, return that target upwards. If it contains both, I am the LCA."

Theory Notes to Remember:

• Core Logic: A node is the LCA in 3 cases:

  1. The targets are in different subtrees (one left, one right).

  2. The current node is one target, and the other target is somewhere in its subtree.

  3. The targets are not found, in which case return None.

• Time Complexity: O(n), where n is the number of nodes. We visit each node once.

• Space Complexity: O(h) for the recursion stack, where h is the tree height.

LeetCode Example: 236. Lowest Common Ancestor of a Binary Tree

def lowestCommonAncestor(root, p, q):
    # Base case: found nothing, or found one of the targets
    if not root or root == p or root == q:
        return root
    
    # Search in left and right subtrees
    left = lowestCommonAncestor(root.left, p, q)
    right = lowestCommonAncestor(root.right, p, q)
    
    # 1. If both returned a non-null value, p and q are in different subtrees.
    # Current node is the LCA.
    if left and right:
        return root
    
    # 2 & 3. Otherwise, p and q are in the same subtree, or only one was found.
    # Return the non-null child result upwards.
    return left if left else right

How to Remember It: Draw a simple tree. Trace the function. Notice how left and right act like "messengers" bringing up the found nodes. When a node gets a non-null message from both sides, it knows it's the meeting point (LCA).

---

Part 4: Serialize and Deserialize a Binary Tree

Serialization is converting a tree into a string format for storage or transmission. Deserialization rebuilds the tree from that string.

Policy: "Use a preorder traversal to convert the tree into a stream of values, using a placeholder (like 'None' or '#') for null nodes to capture the tree's exact structure."

Theory Notes to Remember:

• Why Preorder? "Root-first" ordering makes it easy to rebuild the tree recursively in the same order.

• Why Placeholders? Without markers for null children, we can't uniquely reconstruct the tree. A single traversal sequence without nulls can represent multiple tree shapes.

• Data Structure: A queue is ideal for deserialization to efficiently pop the front of the data stream.

LeetCode Example: 297. Serialize and Deserialize Binary Tree

from collections import deque

class Codec:
    def serialize(self, root):
        """Encodes a tree to a single string."""
        def dfs_serialize(node):
            if not node:
                result.append("None")
                return
            result.append(str(node.val))
            dfs_serialize(node.left)
            dfs_serialize(node.right)
            
        result = []
        dfs_serialize(root)
        return ",".join(result)

    def deserialize(self, data):
        """Decodes your encoded data to tree."""
        if not data:
            return None
        
        # Use a deque to efficiently pop from the front
        node_list = deque(data.split(','))
        
        def dfs_deserialize():
            val = node_list.popleft()
            if val == "None":
                return None
            
            node = TreeNode(int(val))
            node.left = dfs_deserialize()
            node.right = dfs_deserialize()
            return node
            
        return dfs_deserialize()

# Usage:
# ser = Codec()
# deser = Codec()
# ans = deser.deserialize(ser.serialize(root))

How to Remember It: The serialization process is a preorder DFS that writes "None" for leaves. The deserialization process is a preorder DFS that reads from the string; when it reads a "None", it returns a null node. The symmetry makes it beautiful.

---

2-Hour Study Plan & Final Tips

To make the most of this guide in under two hours, follow this plan:

• Minute 0-30: Read Parts 1.1, 1.2, and 1.3 thoroughly. Write down the recursive and iterative code for all three traversals on paper without looking. Understand why the iterative stack works.

• Minute 30-45: Master Part 2 (Level-Order). Note the queue pattern. Solve LeetCode #102.

• Minute 45-75: Deep dive into Part 3 (LCA). This is the most conceptually challenging. Trace the algorithm on a few examples. The "if left and right: return root" line is the soul of the algorithm.

• Minute 75-105: Understand Serialize/Deserialize (Part 4). Pay close attention to why we need null markers.

• Minute 105-120: Solve the linked LeetCode problems without looking at the solutions. This active recall cements the knowledge.

Final Memory Aids

• Preorder: I'm first! (Root -> L -> R)

• Inorder: I'm in the middle! (L -> Root -> R)

• Postorder: I'm last! (L -> R -> Root)

• DFS Stack, BFS Queue.

• LCA: "Find p or q, if a node gets one from left and one from right, it's the LCA."

• Serialize: "Preorder with 'None' placeholders. Deserialize: reverse the process."