LeetCode Patterns ·

🎯 Tree Traversal Patterns

1️⃣ Core Framework

When discussing Tree Traversal Patterns, I frame it as:

What tree traversal means
DFS traversal
Preorder traversal
Inorder traversal
Postorder traversal
Level order traversal
Recursive vs iterative traversal
Tree path problems
Bottom-up recursion
Senior-level explanation

2️⃣ What Problem Are We Solving?

Tree traversal means visiting nodes in a tree in a specific order.

It is commonly used for:

Binary tree traversal
Binary search tree problems
Tree path sum
Tree height / depth
Lowest common ancestor
Validate binary search tree
Serialize and deserialize tree
Construct tree from traversal
Level order traversal
Zigzag traversal
Diameter of binary tree
Balanced binary tree
Subtree problems
Tree dynamic programming

The core idea is:

A tree problem is usually solved by deciding:
what information each node needs,
what information each node returns,
and in what order nodes should be processed.

👉 Interview Answer

Tree traversal is the process of visiting every node in a tree in a controlled order.

DFS traversals include preorder, inorder, and postorder.

BFS traversal visits nodes level by level.

The key is to choose the traversal order based on when we need to process the current node: before children, between children, after children, or level by level.

3️⃣ Basic Tree Node Structure

Binary Tree Node

Most interview problems use this structure:

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

Tree Shape

Example:

Traversal Output

Different traversal orders produce different outputs:

Preorder:  1, 2, 4, 5, 3
Inorder:   4, 2, 5, 1, 3
Postorder: 4, 5, 2, 3, 1
Level:     1, 2, 3, 4, 5

👉 Interview Answer

A binary tree node usually has a value, a left child, and a right child.

The same tree can produce different traversal orders depending on whether we process the current node before, between, or after its children.

4️⃣ DFS Traversal Overview

DFS Means Depth First Search

DFS goes deep before going wide.

For binary trees, DFS usually appears as:

preorder
inorder
postorder

Recursive Shape

Most tree DFS has this shape:

def dfs(node):
    if not node:
        return

    dfs(node.left)
    dfs(node.right)

Key Question

Where do we process node.val?

Before children  -> preorder
Between children -> inorder
After children   -> postorder

👉 Interview Answer

DFS explores a tree by going as deep as possible before backtracking.

In binary trees, the three classic DFS traversals are preorder, inorder, and postorder.

The difference is where we process the current node relative to its children.

5️⃣ Preorder Traversal

Order

Preorder means:

Root
Left
Right

Use Cases

Preorder is useful when:

need to process parent before children
serialize tree
copy tree
construct tree
path tracking top-down

Recursive Code

def preorder_traversal(root):
    result = []

    def dfs(node):
        if not node:
            return

        result.append(node.val)
        dfs(node.left)
        dfs(node.right)

    dfs(root)
    return result

👉 Interview Answer

Preorder traversal processes the current node before its children.

The order is root, left, right.

It is useful when parent information needs to be handled before visiting child nodes, such as serialization, copying a tree, or top-down path problems.

6️⃣ Inorder Traversal

Order

Inorder means:

Left
Root
Right

Special Meaning for BST

For a binary search tree, inorder traversal returns values in sorted order.

Recursive Code

def inorder_traversal(root):
    result = []

    def dfs(node):
        if not node:
            return

        dfs(node.left)
        result.append(node.val)
        dfs(node.right)

    dfs(root)
    return result

👉 Interview Answer

Inorder traversal processes the left subtree, then the current node, then the right subtree.

For a binary search tree, inorder traversal visits nodes in sorted order.

This makes it useful for BST validation, kth smallest element, and sorted tree problems.

7️⃣ Postorder Traversal

Order

Postorder means:

Left
Right
Root

Use Cases

Postorder is useful when:

need children results before parent
tree height
tree diameter
balanced tree
delete tree
subtree computation
bottom-up recursion

Recursive Code

def postorder_traversal(root):
    result = []

    def dfs(node):
        if not node:
            return

        dfs(node.left)
        dfs(node.right)
        result.append(node.val)

    dfs(root)
    return result

👉 Interview Answer

Postorder traversal processes children before the current node.

The order is left, right, root.

It is useful for bottom-up tree problems, where the parent answer depends on information returned from children.

8️⃣ Level Order Traversal

Order

Level order traversal visits nodes level by level.

Example:

Output:

[[1], [2, 3], [4, 5]]

Use BFS

Use queue:

process current level
push next level

Code

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

👉 Interview Answer

Level order traversal uses BFS.

I use a queue and process the tree one level at a time.

For each level, I record the current queue size, process exactly that many nodes, and push their children into the queue.

9️⃣ Recursive vs Iterative Traversal

Recursive Traversal

Recursive traversal is usually simpler.

def dfs(node):
    if not node:
        return

    dfs(node.left)
    dfs(node.right)

Iterative Traversal

Iterative traversal uses a stack or queue.

Use stack for DFS:

preorder
inorder
postorder

Use queue for BFS:

level order

Interview Preference

Most tree problems are easier to explain recursively.

But iterative versions are important when recursion depth may be large.

👉 Interview Answer

Recursive traversal is usually the cleanest way to solve tree problems.

Iterative traversal uses an explicit stack for DFS or a queue for BFS.

Recursion is easier to reason about, while iteration can avoid recursion depth issues.

🔟 Iterative Preorder Traversal

Idea

Preorder is:

Root
Left
Right

Use stack.

Because stack is LIFO, push right child first, then left child.

Code

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)

        if node.left:
            stack.append(node.left)

    return result

👉 Interview Answer

Iterative preorder uses a stack.

I process the current node first.

Since stack is last-in-first-out, I push the right child before the left child, so the left child is processed first.

1️⃣1️⃣ Iterative Inorder Traversal

Idea

Go left as far as possible.

Then process node.

Then go right.

Code

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

👉 Interview Answer

Iterative inorder traversal uses a stack.

I keep pushing left nodes until I reach null.

Then I pop a node, process it, and move to its right subtree.

This simulates the recursive left-root-right order.

1️⃣2️⃣ Iterative Postorder Traversal

Idea

Postorder is:

Left
Right
Root

One simple iterative trick:

Root
Right
Left

Then reverse result.

Code

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

    result = []
    stack = [root]

    while stack:
        node = stack.pop()
        result.append(node.val)

        if node.left:
            stack.append(node.left)

        if node.right:
            stack.append(node.right)

    return result[::-1]

👉 Interview Answer

Iterative postorder is harder than preorder or inorder.

One simple method is to process nodes in root-right-left order, then reverse the result.

After reversing, the order becomes left-right-root, which is postorder.

1️⃣3️⃣ Maximum Depth of Binary Tree

Problem

Find the maximum depth of a binary tree.

Postorder Idea

Depth of current node is:

1 + max(left_depth, right_depth)

Need child results first, so this is bottom-up recursion.

Code

def max_depth(root):
    if not root:
        return 0

    left_depth = max_depth(root.left)
    right_depth = max_depth(root.right)

    return 1 + max(left_depth, right_depth)

👉 Interview Answer

Maximum depth is a postorder-style problem.

I first compute the depth of the left and right subtrees.

Then the depth of the current node is one plus the maximum of those two depths.

1️⃣4️⃣ Minimum Depth of Binary Tree

Problem

Find the minimum depth from root to a leaf.

Important Edge Case

If one child is missing, do not take zero as valid leaf depth.

Wrong:

1 + min(left_depth, right_depth)

This fails when one child is null.

Correct Code

def min_depth(root):
    if not root:
        return 0

    if not root.left:
        return 1 + min_depth(root.right)

    if not root.right:
        return 1 + min_depth(root.left)

    return 1 + min(min_depth(root.left), min_depth(root.right))

👉 Interview Answer

Minimum depth requires care with missing children.

A null child does not represent a valid leaf path.

If one child is missing, I must take the depth of the other child.

Only when both children exist do I take the minimum.

1️⃣5️⃣ Balanced Binary Tree

Problem

Determine whether a binary tree is height-balanced.

A tree is balanced if:

for every node,
left and right subtree heights differ by at most 1

Postorder Idea

Need subtree heights first.

Return:

height if balanced
-1 if not balanced

Code

def is_balanced(root):
    def height(node):
        if not node:
            return 0

        left = height(node.left)
        if left == -1:
            return -1

        right = height(node.right)
        if right == -1:
            return -1

        if abs(left - right) > 1:
            return -1

        return 1 + max(left, right)

    return height(root) != -1

👉 Interview Answer

Balanced Binary Tree is a bottom-up problem.

For each node, I need the height of both subtrees before deciding whether the current node is balanced.

I return -1 early if any subtree is unbalanced, otherwise I return the subtree height.

1️⃣6️⃣ Diameter of Binary Tree

Problem

Find the length of the longest path between any two nodes.

The path may or may not pass through the root.

Key Insight

At each node, a possible diameter is:

left_height + right_height

Need postorder traversal.

Code

def diameter_of_binary_tree(root):
    answer = 0

    def height(node):
        nonlocal answer

        if not node:
            return 0

        left = height(node.left)
        right = height(node.right)

        answer = max(answer, left + right)

        return 1 + max(left, right)

    height(root)
    return answer

👉 Interview Answer

Diameter of Binary Tree is a postorder traversal problem.

At each node, the longest path passing through that node is left height plus right height.

I update a global answer while returning the height of the current subtree to the parent.

1️⃣7️⃣ Path Sum

Problem

Determine whether there is a root-to-leaf path whose sum equals target.

Top-Down DFS

Pass remaining sum down the tree.

At leaf:

remaining == node.val

Code

def has_path_sum(root, target_sum):
    if not root:
        return False

    if not root.left and not root.right:
        return target_sum == root.val

    remaining = target_sum - root.val

    return (
        has_path_sum(root.left, remaining)
        or
        has_path_sum(root.right, remaining)
    )

👉 Interview Answer

Path Sum is a top-down DFS problem.

I subtract the current node value from the remaining target.

When I reach a leaf, I check whether the leaf value equals the remaining target.

1️⃣8️⃣ Path Sum II

Problem

Return all root-to-leaf paths where the sum equals target.

Backtracking

Maintain current path.

At leaf, if sum matches, append a copy of the path.

Code

def path_sum(root, target_sum):
    result = []
    path = []

    def dfs(node, remaining):
        if not node:
            return

        path.append(node.val)

        if not node.left and not node.right and remaining == node.val:
            result.append(path[:])
        else:
            dfs(node.left, remaining - node.val)
            dfs(node.right, remaining - node.val)

        path.pop()

    dfs(root, target_sum)
    return result

👉 Interview Answer

Path Sum II uses DFS with backtracking.

I maintain the current root-to-node path.

When I reach a leaf and the remaining sum matches, I add a copy of the path to the result.

Then I backtrack by removing the current node before returning.

1️⃣9️⃣ Validate Binary Search Tree

BST Rule

For every node:

all values in left subtree < node.val
all values in right subtree > node.val

Inorder Idea

Inorder traversal of a BST should be strictly increasing.

Code

def is_valid_bst(root):
    previous = None

    def inorder(node):
        nonlocal previous

        if not node:
            return True

        if not inorder(node.left):
            return False

        if previous is not None and node.val <= previous:
            return False

        previous = node.val

        return inorder(node.right)

    return inorder(root)

Alternative: Bounds

def is_valid_bst(root):
    def validate(node, low, high):
        if not node:
            return True

        if not (low < node.val < high):
            return False

        return (
            validate(node.left, low, node.val)
            and
            validate(node.right, node.val, high)
        )

    return validate(root, float("-inf"), float("inf"))

👉 Interview Answer

To validate a BST, I can use inorder traversal because a valid BST produces a strictly increasing sequence.

Another robust method is passing lower and upper bounds down the tree.

Each node must be within the valid range determined by its ancestors.

2️⃣0️⃣ Kth Smallest Element in BST

Key Insight

Inorder traversal of BST is sorted.

So kth smallest is the kth node visited in inorder order.

Code

def kth_smallest(root, k):
    stack = []
    current = root

    while current or stack:
        while current:
            stack.append(current)
            current = current.left

        current = stack.pop()
        k -= 1

        if k == 0:
            return current.val

        current = current.right

👉 Interview Answer

In a BST, inorder traversal visits values in sorted order.

Therefore, the kth smallest element is simply the kth value visited during inorder traversal.

An iterative inorder traversal can stop as soon as k reaches zero.

2️⃣1️⃣ Lowest Common Ancestor

Problem

Find the lowest node that has both p and q as descendants.

General Binary Tree

Use postorder recursion.

If current node is p or q, return current node.

If left and right both return non-null, current node is LCA.

Code

def lowest_common_ancestor(root, p, q):
    if not root or root == p or root == q:
        return root

    left = lowest_common_ancestor(root.left, p, q)
    right = lowest_common_ancestor(root.right, p, q)

    if left and right:
        return root

    return left if left else right

👉 Interview Answer

For LCA in a general binary tree, I use postorder recursion.

If the current node is p or q, I return it.

Then I search left and right subtrees.

If both sides return non-null, the current node is the lowest common ancestor.

2️⃣2️⃣ Serialize and Deserialize Binary Tree

Preorder With Null Markers

To serialize a tree uniquely, we need to record null children.

Example:

1,2,#,#,3,#,#

Code

def serialize(root):
    result = []

    def dfs(node):
        if not node:
            result.append("#")
            return

        result.append(str(node.val))
        dfs(node.left)
        dfs(node.right)

    dfs(root)
    return ",".join(result)


def deserialize(data):
    values = iter(data.split(","))

    def dfs():
        value = next(values)

        if value == "#":
            return None

        node = TreeNode(int(value))
        node.left = dfs()
        node.right = dfs()

        return node

    return dfs()

👉 Interview Answer

Serialize and Deserialize Binary Tree can be solved with preorder traversal and null markers.

Preorder records the root before children.

Null markers are necessary to preserve tree structure.

During deserialization, I consume values in preorder order and recursively rebuild the tree.

2️⃣3️⃣ Construct Binary Tree From Traversals

Common Problem

Given:

preorder
inorder

Build the original binary tree.

Key Idea

Preorder tells root first.

Inorder tells left and right subtree boundary.

Code

def build_tree(preorder, inorder):
    index_map = {}

    for i, value in enumerate(inorder):
        index_map[value] = i

    preorder_index = 0

    def build(left, right):
        nonlocal preorder_index

        if left > right:
            return None

        root_val = preorder[preorder_index]
        preorder_index += 1

        root = TreeNode(root_val)

        mid = index_map[root_val]

        root.left = build(left, mid - 1)
        root.right = build(mid + 1, right)

        return root

    return build(0, len(inorder) - 1)

👉 Interview Answer

To build a tree from preorder and inorder, preorder gives the root of each subtree.

Inorder tells where the left subtree and right subtree split.

I use a hashmap to find root positions in inorder quickly, then recursively build left and right subtrees.

2️⃣4️⃣ Common Edge Cases

Empty Tree

root = None

Return depends on problem:

[]
0
False
None

Single Node

Usually both left and right are null.

Skewed Tree

Example:

Depth can be O(n).

May cause recursion depth issue.

Duplicate Values

Some BST and construction problems assume unique values.

If duplicates exist, logic may need adjustment.

Null Children

Serialization and traversal problems often require explicit null handling.

👉 Interview Answer

Common tree traversal edge cases include empty trees, single-node trees, skewed trees, duplicate values, and null children.

Skewed trees are especially important because recursion depth can become O(n).

2️⃣5️⃣ Common Mistakes

Mistake 1: Confusing Traversal Orders

Preorder:  root, left, right
Inorder:   left, root, right
Postorder: left, right, root

Mistake 2: Forgetting Base Case

Every recursive tree function needs:

if not node:
    return ...

Mistake 3: Using Inorder for Non-BST Sorting

Inorder is sorted only for BST, not for general binary trees.

Mistake 4: Not Copying Path in Backtracking

Wrong:

result.append(path)

Correct:

result.append(path[:])

Mistake 5: Incorrect Minimum Depth Logic

Null child is not a valid leaf path.

Mistake 6: Global Answer Not Updated Correctly

Problems like diameter need:

nonlocal answer

👉 Interview Answer

Common tree traversal mistakes include mixing up preorder, inorder, and postorder, forgetting the null base case, assuming inorder is sorted for any binary tree, not copying paths during backtracking, mishandling minimum depth, and forgetting to update global answers correctly.

2️⃣6️⃣ When Tree Traversal Applies

Good Fit

Use tree traversal when the problem asks for:

visit all nodes
compute tree height
find path
validate tree property
compare trees
serialize tree
construct tree
find ancestor
level order output
bottom-up subtree information

Problem Signals

Look for words like:

tree
root
leaf
subtree
ancestor
descendant
path
height
depth
level
BST
serialize
traversal

👉 Interview Answer

I consider tree traversal whenever the problem involves visiting nodes, computing information from subtrees, finding root-to-leaf paths, validating a tree property, or processing levels.

Then I choose preorder, inorder, postorder, or BFS based on when the current node should be processed.

2️⃣7️⃣ When Tree Traversal Does Not Apply

Not Good Fit

Tree traversal alone may not be enough when:

need shortest path in general graph
tree has parent pointers and repeated queries
need dynamic updates
need range query on tree
need lowest common ancestor at scale

Better Alternatives

Problem Type	Better Pattern
General graph shortest path	BFS / Dijkstra
Many LCA queries	Binary Lifting
Dynamic tree updates	Segment Tree / Fenwick on Euler Tour
Tree range queries	Euler Tour + Segment Tree
Dependency graph	Topological Sort
Cyclic graph traversal	Graph DFS with visited

👉 Interview Answer

Basic tree traversal is powerful, but it may not be enough for repeated queries or dynamic updates.

For many LCA queries, binary lifting may be better.

For subtree range queries, Euler tour plus Segment Tree may be needed.

For general graphs with cycles, graph traversal with visited state is required.

2️⃣8️⃣ Standard Templates

Recursive DFS Template

def dfs(node):
    if not node:
        return

    dfs(node.left)
    dfs(node.right)

Preorder Template

def preorder(node):
    if not node:
        return

    process(node)
    preorder(node.left)
    preorder(node.right)

Inorder Template

def inorder(node):
    if not node:
        return

    inorder(node.left)
    process(node)
    inorder(node.right)

Postorder Template

def postorder(node):
    if not node:
        return value_for_null

    left = postorder(node.left)
    right = postorder(node.right)

    return combine(left, right, node)

Level Order Template

from collections import deque

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

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

    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

Path Backtracking Template

def dfs(node):
    if not node:
        return

    path.append(node.val)

    if not node.left and not node.right:
        process(path)
    else:
        dfs(node.left)
        dfs(node.right)

    path.pop()

🧠 Staff-Level Answer Final

👉 Interview Answer Full Version

Tree traversal is the process of visiting nodes in a tree in a specific order.

The most common traversal patterns are preorder, inorder, postorder, and level order.

Preorder processes the current node before its children. The order is root, left, right. This is useful when parent information needs to be handled before children, such as serialization, copying a tree, or top-down path problems.

Inorder processes left subtree, current node, then right subtree. For a binary search tree, inorder traversal produces values in sorted order. This is useful for BST validation, kth smallest element, and problems that depend on sorted BST order.

Postorder processes children before the current node. The order is left, right, root. This is useful for bottom-up problems, where the parent answer depends on information from children. Examples include maximum depth, balanced binary tree, diameter of binary tree, and subtree computations.

Level order traversal uses BFS. It processes nodes level by level using a queue. This is useful when the problem asks for levels, width, right side view, zigzag traversal, or minimum depth.

A key way to solve tree problems is to define what each recursive call returns. For height problems, the recursive call returns subtree height. For balanced tree, it may return height or -1 if unbalanced. For LCA, it returns whether p or q is found in the subtree.

For path problems, I usually use top-down DFS and backtracking. I maintain the current path, process it at leaf nodes, and then pop the current node when returning.

For BST problems, inorder traversal or boundary recursion is often the core idea. Inorder is sorted only for valid BSTs, not for arbitrary binary trees.

Recursive traversal is usually simplest, but iterative traversal with a stack can avoid recursion depth issues.

At a senior level, I would explain: what each node needs from its parent, what each node needs from its children, when the current node should be processed, what the recursive function returns, and whether DFS or BFS better matches the problem.

⭐ Final Insight

Tree Traversal Patterns 的核心不是“背 preorder / inorder / postorder”。

它的核心是判断当前 node 的处理时机：

parent before children 用 preorder， BST sorted order 用 inorder， children before parent 用 postorder， level-by-level 用 BFS。

Senior-level 的重点是：

recursive function 返回什么，当前 node 需要 children 的什么信息， path 是否需要 backtracking，是否是 BST，是否需要 level information，空树和 skewed tree 怎么处理，以及什么时候 iterative traversal 更安全。

能讲清楚这些， Tree Traversal 就是一类处理 subtree information、path information、BST order 和 level structure 的核心模式。

中文部分

🎯 Tree Traversal Patterns

1️⃣ 核心框架

讨论 Tree Traversal Patterns 时，我通常从：

Tree traversal 是什么
DFS traversal
Preorder traversal
Inorder traversal
Postorder traversal
Level order traversal
Recursive vs iterative traversal
Tree path problems
Bottom-up recursion
高级工程师解释方式

2️⃣ 要解决什么问题？

Tree traversal 指的是按照某种顺序访问 tree 中的 nodes。

它常用于：

Binary tree traversal
Binary search tree problems
Tree path sum
Tree height / depth
Lowest common ancestor
Validate binary search tree
Serialize and deserialize tree
Construct tree from traversal
Level order traversal
Zigzag traversal
Diameter of binary tree
Balanced binary tree
Subtree problems
Tree dynamic programming

核心思想是：

Tree problem 通常要先决定：
每个 node 需要什么信息，
每个 node 返回什么信息，
以及 node 应该在什么时候被处理。

👉 面试回答

Tree traversal 是按照某种顺序访问 tree 中所有 nodes 的过程。

DFS traversal 包括 preorder、inorder 和 postorder。

BFS traversal 会按 level 一层一层访问 nodes。

关键是根据当前 node 什么时候需要被处理，来选择 traversal order：在 children 前处理，在左右 children 中间处理，在 children 后处理，或者 level by level 处理。

3️⃣ Basic Tree Node Structure

Binary Tree Node

大多数面试题使用这个结构：

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

Tree Shape

Example:

Traversal Output

不同 traversal order 会产生不同输出：

Preorder:  1, 2, 4, 5, 3
Inorder:   4, 2, 5, 1, 3
Postorder: 4, 5, 2, 3, 1
Level:     1, 2, 3, 4, 5

👉 面试回答

Binary tree node 通常有一个 value、一个 left child、一个 right child。

同一棵树根据当前 node 的处理位置不同，可以产生 preorder、inorder、postorder 或 level order 等不同 traversal 结果。

4️⃣ DFS Traversal Overview

DFS Means Depth First Search

DFS 会先往深处走，再 backtrack。

对于 binary tree， DFS 通常有三种形式：

preorder
inorder
postorder

Recursive Shape

大多数 tree DFS 都是这个形状：

def dfs(node):
    if not node:
        return

    dfs(node.left)
    dfs(node.right)

Key Question

在哪里处理 node.val？

Before children  -> preorder
Between children -> inorder
After children   -> postorder

👉 面试回答

DFS 会尽可能先深入 tree，然后再回溯。

在 binary tree 中，三种经典 DFS traversal 是 preorder、inorder 和 postorder。

它们的区别在于当前 node 是在 children 之前、中间还是之后被处理。

5️⃣ Preorder Traversal

Order

Preorder 是：

Root
Left
Right

Use Cases

Preorder 适合：

need to process parent before children
serialize tree
copy tree
construct tree
path tracking top-down

Recursive Code

def preorder_traversal(root):
    result = []

    def dfs(node):
        if not node:
            return

        result.append(node.val)
        dfs(node.left)
        dfs(node.right)

    dfs(root)
    return result

👉 面试回答

Preorder traversal 会在 children 之前处理当前 node。

顺序是 root、left、right。

它适合 parent information 需要先于 children 被处理的场景，比如 serialization、copy tree，或者 top-down path problems。

6️⃣ Inorder Traversal

Order

Inorder 是：

Left
Root
Right

Special Meaning for BST

对于 binary search tree， inorder traversal 会得到 sorted order。

Recursive Code

def inorder_traversal(root):
    result = []

    def dfs(node):
        if not node:
            return

        dfs(node.left)
        result.append(node.val)
        dfs(node.right)

    dfs(root)
    return result

👉 面试回答

Inorder traversal 会先处理 left subtree，再处理当前 node，最后处理 right subtree。

对 binary search tree 来说， inorder traversal 会按照 sorted order 访问 nodes。

这使它适合 BST validation、kth smallest element，以及和 sorted tree order 有关的问题。

7️⃣ Postorder Traversal

Order

Postorder 是：

Left
Right
Root

Use Cases

Postorder 适合：

need children results before parent
tree height
tree diameter
balanced tree
delete tree
subtree computation
bottom-up recursion

Recursive Code

def postorder_traversal(root):
    result = []

    def dfs(node):
        if not node:
            return

        dfs(node.left)
        dfs(node.right)
        result.append(node.val)

    dfs(root)
    return result

👉 面试回答

Postorder traversal 会先处理 children，再处理当前 node。

顺序是 left、right、root。

它适合 bottom-up tree problems，也就是 parent 的答案依赖 children 返回信息的场景。

8️⃣ Level Order Traversal

Order

Level order traversal 会一层一层访问 nodes。

Example:

Output:

[[1], [2, 3], [4, 5]]

Use BFS

使用 queue：

process current level
push next level

Code

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

👉 面试回答

Level order traversal 使用 BFS。

我用 queue 按层处理 tree。

每一层先记录当前 queue size，然后只处理这一层的 nodes，并把它们的 children 加入 queue。

9️⃣ Recursive vs Iterative Traversal

Recursive Traversal

Recursive traversal 通常更简单。

def dfs(node):
    if not node:
        return

    dfs(node.left)
    dfs(node.right)

Iterative Traversal

Iterative traversal 使用 stack 或 queue。

DFS 使用 stack：

preorder
inorder
postorder

BFS 使用 queue：

level order

Interview Preference

大多数 tree problems 用 recursion 更容易解释。

但当 recursion depth 很大时， iterative version 更安全。

👉 面试回答

Recursive traversal 通常是解决 tree problems 最清晰的方式。

Iterative traversal 会使用 explicit stack 做 DFS，或者使用 queue 做 BFS。

Recursion 更容易推理， iteration 可以避免 recursion depth 问题。

🔟 Iterative Preorder Traversal

Idea

Preorder 是：

Root
Left
Right

使用 stack。

因为 stack 是 LIFO，所以先 push right child，再 push left child。

Code

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)

        if node.left:
            stack.append(node.left)

    return result

👉 面试回答

Iterative preorder 使用 stack。

我先处理当前 node。

因为 stack 是 last-in-first-out，所以要先 push right child，再 push left child，这样 left child 会先被处理。

1️⃣1️⃣ Iterative Inorder Traversal

Idea

一直向左走到底。

然后处理 node。

然后转向右 subtree。

Code

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

👉 面试回答

Iterative inorder traversal 使用 stack。

我不断把 left nodes push 到 stack，直到 current 为空。

然后 pop 一个 node，处理它，再移动到它的 right subtree。

这个过程模拟了 recursive left-root-right order。

1️⃣2️⃣ Iterative Postorder Traversal

Idea

Postorder 是：

Left
Right
Root

一个简单技巧是先得到：

Root
Right
Left

然后 reverse result。

Code

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

    result = []
    stack = [root]

    while stack:
        node = stack.pop()
        result.append(node.val)

        if node.left:
            stack.append(node.left)

        if node.right:
            stack.append(node.right)

    return result[::-1]

👉 面试回答

Iterative postorder 比 preorder 和 inorder 更难。

一个简单方法是先按 root-right-left 的顺序处理，然后把结果 reverse。

Reverse 之后就是 left-right-root，也就是 postorder。

1️⃣3️⃣ Maximum Depth of Binary Tree

Problem

求 binary tree 的 maximum depth。

Postorder Idea

当前 node 的 depth 是：

1 + max(left_depth, right_depth)

需要先知道 children results，所以这是 bottom-up recursion。

Code

def max_depth(root):
    if not root:
        return 0

    left_depth = max_depth(root.left)
    right_depth = max_depth(root.right)

    return 1 + max(left_depth, right_depth)

👉 面试回答

Maximum depth 是 postorder-style problem。

我先计算 left subtree 和 right subtree 的 depth。

然后当前 node 的 depth 是两边最大值加一。

1️⃣4️⃣ Minimum Depth of Binary Tree

Problem

找从 root 到 leaf 的 minimum depth。

Important Edge Case

如果一个 child 缺失，不能把 0 当成 valid leaf depth。

错误写法：

1 + min(left_depth, right_depth)

当一个 child 是 null 时会出错。

Correct Code

def min_depth(root):
    if not root:
        return 0

    if not root.left:
        return 1 + min_depth(root.right)

    if not root.right:
        return 1 + min_depth(root.left)

    return 1 + min(min_depth(root.left), min_depth(root.right))

👉 面试回答

Minimum depth 要特别注意 missing children。

Null child 不代表一条 valid leaf path。

如果一个 child 缺失，必须选择另一个 child 的 depth。

只有左右 children 都存在时，才能取 minimum。

1️⃣5️⃣ Balanced Binary Tree

Problem

判断 binary tree 是否 height-balanced。

Balanced 表示：

对每个 node，
left 和 right subtree heights 的差不超过 1

Postorder Idea

先需要 subtree heights。

height if balanced
-1 if not balanced

Code

def is_balanced(root):
    def height(node):
        if not node:
            return 0

        left = height(node.left)
        if left == -1:
            return -1

        right = height(node.right)
        if right == -1:
            return -1

        if abs(left - right) > 1:
            return -1

        return 1 + max(left, right)

    return height(root) != -1

👉 面试回答

Balanced Binary Tree 是 bottom-up problem。

对每个 node，我需要先知道 left 和 right subtree 的 height，才能判断当前 node 是否 balanced。

如果任何 subtree 已经 unbalanced，就提前返回 -1。

否则返回当前 subtree 的 height。

1️⃣6️⃣ Diameter of Binary Tree

Problem

找 binary tree 中任意两个 nodes 之间的最长 path 长度。

这个 path 不一定经过 root。

Key Insight

在每个 node，经过当前 node 的 possible diameter 是：

left_height + right_height

需要 postorder traversal。

Code

def diameter_of_binary_tree(root):
    answer = 0

    def height(node):
        nonlocal answer

        if not node:
            return 0

        left = height(node.left)
        right = height(node.right)

        answer = max(answer, left + right)

        return 1 + max(left, right)

    height(root)
    return answer

👉 面试回答

Diameter of Binary Tree 是 postorder traversal problem。

对每个 node，经过它的最长 path 是 left height 加 right height。

我一边返回当前 subtree height 给 parent，一边更新全局最大 diameter。

1️⃣7️⃣ Path Sum

Problem

判断是否存在一条 root-to-leaf path，其 sum 等于 target。

Top-Down DFS

把 remaining sum 向下传递。

到 leaf 时检查：

remaining == node.val

Code

def has_path_sum(root, target_sum):
    if not root:
        return False

    if not root.left and not root.right:
        return target_sum == root.val

    remaining = target_sum - root.val

    return (
        has_path_sum(root.left, remaining)
        or
        has_path_sum(root.right, remaining)
    )

👉 面试回答

Path Sum 是 top-down DFS problem。

我会从 target 中减去当前 node value，把 remaining sum 传给 children。

当到达 leaf 时，检查 leaf value 是否等于 remaining target。

1️⃣8️⃣ Path Sum II

Problem

返回所有 root-to-leaf paths，其中 path sum 等于 target。

Backtracking

维护 current path。

到 leaf 时，如果 sum match，就把 path 的 copy 加入 result。

Code

def path_sum(root, target_sum):
    result = []
    path = []

    def dfs(node, remaining):
        if not node:
            return

        path.append(node.val)

        if not node.left and not node.right and remaining == node.val:
            result.append(path[:])
        else:
            dfs(node.left, remaining - node.val)
            dfs(node.right, remaining - node.val)

        path.pop()

    dfs(root, target_sum)
    return result

👉 面试回答

Path Sum II 使用 DFS + backtracking。

我维护当前 root-to-node path。

当到达 leaf 且 remaining sum match 时，把 path 的 copy 加入 result。

返回前要 pop 当前 node，恢复 path 状态。

1️⃣9️⃣ Validate Binary Search Tree

BST Rule

对每个 node：

left subtree 中所有值 < node.val
right subtree 中所有值 > node.val

Inorder Idea

BST 的 inorder traversal 应该是严格递增的。

Code

def is_valid_bst(root):
    previous = None

    def inorder(node):
        nonlocal previous

        if not node:
            return True

        if not inorder(node.left):
            return False

        if previous is not None and node.val <= previous:
            return False

        previous = node.val

        return inorder(node.right)

    return inorder(root)

Alternative: Bounds

def is_valid_bst(root):
    def validate(node, low, high):
        if not node:
            return True

        if not (low < node.val < high):
            return False

        return (
            validate(node.left, low, node.val)
            and
            validate(node.right, node.val, high)
        )

    return validate(root, float("-inf"), float("inf"))

👉 面试回答

Validate BST 可以用 inorder traversal，因为 valid BST 的 inorder sequence 必须严格递增。

另一个更稳健的方法是传递 lower 和 upper bounds。

每个 node 的 value 必须满足 ancestors 决定的有效范围。

2️⃣0️⃣ Kth Smallest Element in BST

Key Insight

BST 的 inorder traversal 是 sorted order。

所以 kth smallest 就是 inorder 访问到的第 k 个 node。

Code

def kth_smallest(root, k):
    stack = []
    current = root

    while current or stack:
        while current:
            stack.append(current)
            current = current.left

        current = stack.pop()
        k -= 1

        if k == 0:
            return current.val

        current = current.right

👉 面试回答

在 BST 中， inorder traversal 会按 sorted order 访问 values。

所以 kth smallest element 就是 inorder traversal 中第 k 个访问到的 value。

用 iterative inorder 可以在 k 变成 0 时提前停止。

2️⃣1️⃣ Lowest Common Ancestor

Problem

找到同时拥有 p 和 q 作为 descendants 的最低 node。

General Binary Tree

使用 postorder recursion。

如果当前 node 是 p 或 q，返回当前 node。

如果 left 和 right 都返回 non-null，当前 node 就是 LCA。

Code

def lowest_common_ancestor(root, p, q):
    if not root or root == p or root == q:
        return root

    left = lowest_common_ancestor(root.left, p, q)
    right = lowest_common_ancestor(root.right, p, q)

    if left and right:
        return root

    return left if left else right

👉 面试回答

General binary tree 中的 LCA 可以用 postorder recursion。

如果当前 node 是 p 或 q，返回当前 node。

然后分别搜索 left 和 right subtrees。

如果两边都返回 non-null，说明 p 和 q 分别在两边，当前 node 就是 lowest common ancestor。

2️⃣2️⃣ Serialize and Deserialize Binary Tree

Preorder With Null Markers

为了唯一表示一棵 tree，需要记录 null children。

Example:

1,2,#,#,3,#,#

Code

def serialize(root):
    result = []

    def dfs(node):
        if not node:
            result.append("#")
            return

        result.append(str(node.val))
        dfs(node.left)
        dfs(node.right)

    dfs(root)
    return ",".join(result)


def deserialize(data):
    values = iter(data.split(","))

    def dfs():
        value = next(values)

        if value == "#":
            return None

        node = TreeNode(int(value))
        node.left = dfs()
        node.right = dfs()

        return node

    return dfs()

👉 面试回答

Serialize and Deserialize Binary Tree 可以用 preorder traversal 加 null markers。

Preorder 会先记录 root，再记录 children。

Null markers 很重要，因为它们可以保留 tree structure。

Deserialize 时，按 preorder 顺序消费 values，递归重建 tree。

2️⃣3️⃣ Construct Binary Tree From Traversals

Common Problem

给定：

preorder
inorder

构建原来的 binary tree。

Key Idea

Preorder 第一个元素是 root。

Inorder 可以告诉我们 left subtree 和 right subtree 的边界。

Code

def build_tree(preorder, inorder):
    index_map = {}

    for i, value in enumerate(inorder):
        index_map[value] = i

    preorder_index = 0

    def build(left, right):
        nonlocal preorder_index

        if left > right:
            return None

        root_val = preorder[preorder_index]
        preorder_index += 1

        root = TreeNode(root_val)

        mid = index_map[root_val]

        root.left = build(left, mid - 1)
        root.right = build(mid + 1, right)

        return root

    return build(0, len(inorder) - 1)

👉 面试回答

用 preorder 和 inorder 构建 tree 时， preorder 告诉我每个 subtree 的 root。

inorder 告诉我 root 左边是 left subtree，右边是 right subtree。

我用 hashmap 快速找到 root 在 inorder 中的位置，然后递归构建左右 subtrees。

2️⃣4️⃣ 常见 Edge Cases

Empty Tree

root = None

返回值取决于问题：

[]
0
False
None

Single Node

通常 left 和 right 都是 null。

Skewed Tree

Example:

Depth 可能是 O(n)。

可能导致 recursion depth issue。

Duplicate Values

部分 BST 和 construction problems 默认 values unique。

如果有 duplicates，逻辑可能要调整。

Null Children

Serialization 和 traversal problems 经常需要显式处理 null。

👉 面试回答

Tree traversal 常见 edge cases 包括 empty tree、 single-node tree、 skewed tree、 duplicate values，以及 null children。

Skewed tree 特别重要，因为 recursion depth 可能退化成 O(n)。

2️⃣5️⃣ 常见错误

Mistake 1: 混淆 Traversal Orders

Preorder:  root, left, right
Inorder:   left, root, right
Postorder: left, right, root

Mistake 2: 忘记 Base Case

每个 recursive tree function 都需要：

if not node:
    return ...

Mistake 3: 对 Non-BST 使用 Inorder Sorted 假设

Inorder 只有在 BST 中才是 sorted。

普通 binary tree 的 inorder 不一定 sorted。

Mistake 4: Backtracking 中没有 Copy Path

错误：

result.append(path)

正确：

result.append(path[:])

Mistake 5: Minimum Depth Logic 错误

Null child 不是 valid leaf path。

Mistake 6: Global Answer 更新错误

Diameter 这类问题需要：

nonlocal answer

👉 面试回答

Tree traversal 常见错误包括：混淆 preorder、inorder 和 postorder，忘记 null base case，错误假设任意 binary tree 的 inorder 都是 sorted， backtracking 时没有 copy path， minimum depth 对 null child 处理错误，以及没有正确更新 global answer。

2️⃣6️⃣ 什么时候 Tree Traversal 适用？

Good Fit

当题目问：

visit all nodes
compute tree height
find path
validate tree property
compare trees
serialize tree
construct tree
find ancestor
level order output
bottom-up subtree information

Problem Signals

看到这些关键词想到 tree traversal：

tree
root
leaf
subtree
ancestor
descendant
path
height
depth
level
BST
serialize
traversal

👉 面试回答

当问题涉及访问 nodes、从 subtrees 计算信息、查找 root-to-leaf paths、验证 tree property，或按 level 处理 nodes 时，我会考虑 tree traversal。

然后根据 current node 应该什么时候处理，选择 preorder、inorder、postorder 或 BFS。

2️⃣7️⃣ 什么时候 Tree Traversal 不适用？

Not Good Fit

Tree traversal alone 不一定足够：

need shortest path in general graph
tree has parent pointers and repeated queries
need dynamic updates
need range query on tree
need lowest common ancestor at scale

Better Alternatives

Problem Type	Better Pattern
General graph shortest path	BFS / Dijkstra
Many LCA queries	Binary Lifting
Dynamic tree updates	Segment Tree / Fenwick on Euler Tour
Tree range queries	Euler Tour + Segment Tree
Dependency graph	Topological Sort
Cyclic graph traversal	Graph DFS with visited

👉 面试回答

Basic tree traversal 很强，但对于 repeated queries 或 dynamic updates 可能不够。

如果有大量 LCA queries， binary lifting 可能更合适。

如果需要 subtree range queries，可能需要 Euler tour 加 Segment Tree。

如果是带 cycle 的 general graph，需要 graph traversal 和 visited state。

2️⃣8️⃣ 标准模板

Recursive DFS Template

def dfs(node):
    if not node:
        return

    dfs(node.left)
    dfs(node.right)

Preorder Template

def preorder(node):
    if not node:
        return

    process(node)
    preorder(node.left)
    preorder(node.right)

Inorder Template

def inorder(node):
    if not node:
        return

    inorder(node.left)
    process(node)
    inorder(node.right)

Postorder Template

def postorder(node):
    if not node:
        return value_for_null

    left = postorder(node.left)
    right = postorder(node.right)

    return combine(left, right, node)

Level Order Template

from collections import deque

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

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

    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

Path Backtracking Template

def dfs(node):
    if not node:
        return

    path.append(node.val)

    if not node.left and not node.right:
        process(path)
    else:
        dfs(node.left)
        dfs(node.right)

    path.pop()

🧠 Staff-Level Answer Final

👉 面试回答完整版本

Tree traversal 是按照特定顺序访问 tree nodes 的过程。

最常见的 traversal patterns 包括 preorder、inorder、postorder 和 level order。

Preorder 会在 children 之前处理当前 node。顺序是 root、left、right。它适合 parent information 需要先被处理的情况，比如 serialization、copy tree 或 top-down path problems。

Inorder 会先处理 left subtree，再处理当前 node，最后处理 right subtree。对 BST 来说， inorder traversal 会得到 sorted order。所以它适合 BST validation、kth smallest，以及依赖 BST sorted order 的问题。

Postorder 会在 current node 之前先处理 children。顺序是 left、right、root。它适合 bottom-up problems，也就是 parent 的答案依赖 children 的返回信息。例子包括 maximum depth、balanced binary tree、 diameter of binary tree 和 subtree computation。

Level order traversal 使用 BFS。它用 queue 按 level 访问 nodes。当题目问 levels、width、right side view、 zigzag traversal 或 minimum depth 时， BFS 通常很自然。

解决 tree problems 的关键是定义 recursive call 返回什么。对 height problems， recursive call 返回 subtree height。对 balanced tree，可以返回 height 或 -1 表示 unbalanced。对 LCA， recursive call 返回当前 subtree 是否包含 p 或 q。

对 path problems，我通常使用 top-down DFS 和 backtracking。维护 current path，在 leaf node 处理 path，然后返回前 pop 当前 node。

对 BST problems， inorder traversal 或 bounds recursion 经常是核心。需要注意： inorder 只有在 BST 中才代表 sorted order，普通 binary tree 不一定。

Recursive traversal 通常最简单，但 iterative traversal with stack 可以避免 recursion depth issue。

高级工程师解释 tree traversal 时，我会讲清楚：当前 node 需要 parent 的什么信息，当前 node 需要 children 的什么信息，当前 node 应该在什么时候被处理， recursive function 返回什么，以及 DFS 或 BFS 哪个更符合题目要求。

⭐ Final Insight

Tree Traversal Patterns 的核心不是“背 preorder / inorder / postorder”。

它的核心是判断当前 node 的处理时机：

parent before children 用 preorder， BST sorted order 用 inorder， children before parent 用 postorder， level-by-level 用 BFS。

Senior-level 的重点是：

recursive function 返回什么，当前 node 需要 children 的什么信息， path 是否需要 backtracking，是否是 BST，是否需要 level information，空树和 skewed tree 怎么处理，以及什么时候 iterative traversal 更安全。

能讲清楚这些， Tree Traversal 就是一类处理 subtree information、path information、BST order 和 level structure 的核心模式。