Advanced Tree Traversals

Beyond Simple Traversal

You're likely familiar with the classic tree traversals: in-order, pre-order, and post-order. They're the bread and butter of visiting every node. But what about manipulating the tree's structure in more complex ways? How do you save a tree to a file and load it back later? Or view it from a different perspective, like looking at it from the side? These operations require moving beyond simple recursion and thinking about how to encode and decode the tree's very structure.

Saving and Rebuilding Trees

Serialisation is the process of converting a data structure, like a tree, into a format that can be stored or transmitted. Deserialisation is the reverse process, rebuilding the structure from that data. A common way to do this for a binary tree is with a pre-order traversal.

When we serialise, we visit the current node, then its left subtree, then its right subtree. The key is to also record when a child is missing.

We can use a special marker, like "null" or "#", to represent a null node. This is crucial. Without it, you couldn't tell the difference between a node with one child and a node with two. For example, a tree with root 3 and a left child 9 is different from a tree with root 3 and a right child 9. The null marker for the empty branch makes this distinction clear.

# Python example for serialising a binary tree

def serialize(root):
    if not root:
        return "null,"
    
    # Pre-order: root, left, right
    result = str(root.val) + ","
    result += serialize(root.left)
    result += serialize(root.right)
    return result

# Example usage:
# For a tree like:
#     1
#    / \
#   2   3
#      / \
#     4   5
# The output would be: "1,2,null,null,3,4,null,null,5,null,null,"

To deserialise, we can split the string into a list and use a queue to process the nodes in the same pre-order sequence. We build the tree from the top down, taking the first value for the root, then recursively building its left and right children from the subsequent values in the queue.

from collections import deque

def deserialize(data):
    nodes = deque(data.split(','))
    
    def build_tree():
        val = nodes.popleft()
        if val == 'null':
            return None
        
        node = TreeNode(int(val))
        node.left = build_tree()
        node.right = build_tree()
        return node

    return build_tree()

# TreeNode class definition would be needed
class TreeNode:
    def __init__(self, x):
        self.val = x
        self.left = None
        self.right = None

Vertical Order Traversal

Imagine drawing vertical lines through a binary tree. A vertical order traversal visits all nodes on the same vertical line, moving from left to right. To achieve this, we can assign coordinates to each node.

The root is at column 0. A left child is at column - 1, and a right child is at column + 1. We can use a Level-Order Traversal (BFS) to explore the tree. As we visit each node, we store its value in a dictionary or hash map where the key is the column number.

One small complication: nodes in the same column must be sorted by their row (or level). If they are at the same level, they should be sorted by their value. BFS naturally handles the row sorting because we visit nodes level by level. We just need to append nodes to the list for each column.

from collections import defaultdict, deque

def verticalOrder(root):
    if not root:
        return []

    column_table = defaultdict(list)
    queue = deque([(root, 0)]) # (node, column)
    min_col, max_col = 0, 0

    while queue:
        node, col = queue.popleft()

        if node:
            column_table[col].append(node.val)
            min_col = min(min_col, col)
            max_col = max(max_col, col)

            queue.append((node.left, col - 1))
            queue.append((node.right, col + 1))
    
    result = []
    for col in range(min_col, max_col + 1):
        result.append(column_table[col])
        
    return result

# For the tree in the diagram, the output would be:
# [[2, 7], [1, 4, 5], [3], [6]]
# (Note: 4 and 5 are in the same column and level, so their order doesn't matter unless specified)
# If strict sorting by value is needed for same row/col, we'd need to store (row, val) tuples and sort.

Finding Common Ground

The (LCA) of two nodes p and q in a tree is the lowest (deepest) node that has both p and q as descendants. This is a classic problem with an elegant recursive solution.

The recursive function traverses the tree. For any given node:

If the node is null, or if it's one of the nodes we're looking for (p or q), we return the node itself.
Otherwise, we recursively search in the left and right subtrees.
After the recursive calls return, we inspect the results. If both the left and right calls returned a non-null node, it means p was found in one subtree and q in the other. Therefore, the current node is their LCA.
If only one of the calls returned a node, it means both p and q are in that subtree. We pass that result up the call stack. This node will eventually be identified as the LCA higher up, or one of the nodes is an ancestor of the other.

def lowestCommonAncestor(root, p, q):
    # Base case: if root is null or one of the nodes
    if not root or root == p or root == q:
        return root

    # Recurse on left and right subtrees
    left_lca = lowestCommonAncestor(root.left, p, q)
    right_lca = lowestCommonAncestor(root.right, p, q)

    # If both subtrees returned a node, this is the LCA
    if left_lca and right_lca:
        return root

    # Otherwise, return the subtree that found a node
    return left_lca if left_lca is not None else right_lca

This approach works for any binary tree, not just a Binary Search Tree. For a BST, you can use the node values to find the LCA more efficiently by checking if p and q are on opposite sides of the current node.

Recursive vs. Iterative DFS

Depth-First Search (DFS) can be implemented recursively or iteratively. The recursive approach is often more concise and maps directly to the definition of a tree. The system's call stack manages the state for you.

# Recursive In-order Traversal (a type of DFS)
def dfs_recursive(node):
    if not node:
        return
    dfs_recursive(node.left)
    # visit(node)
    dfs_recursive(node.right)

However, recursion has a downside: for a very deep or unbalanced tree, you can run into a error. The call stack has a limited size. An iterative approach using your own explicit stack avoids this problem.

An iterative pre-order traversal is straightforward. You push the root onto a stack. Then, in a loop, you pop a node, process it, and push its right child, then its left child. Pushing the right child first ensures the left child is processed first, maintaining the pre-order sequence.

# Iterative Pre-order Traversal (a type of DFS)
def dfs_iterative(root):
    if not root:
        return []
    
    stack = [root]
    result = []
    
    while stack:
        node = stack.pop()
        result.append(node.val)
        
        # Push right child first, so left is processed first
        if node.right:
            stack.append(node.right)
        if node.left:
            stack.append(node.left)
            
    return result

Iterative in-order and post-order traversals are more complex but follow a similar principle of using a stack to manually simulate the recursion.

Let's check your understanding of these advanced traversal techniques.

Quiz Questions 1/6

When serialising a binary tree using pre-order traversal, why is it crucial to include a special marker (like '#' or 'null') for empty children?

Quiz Questions 2/6

To deserialise a tree from a pre-order traversal string (e.g., "1,2,#,#,3,#,#"), a common and efficient approach is to first split the string into a list and then process the elements using a __________.

Mastering these methods allows you to not just visit nodes, but to fundamentally reshape and analyze tree structures, a key skill for complex algorithmic problems.

Mastering the Meta Coding Interview