LeetCode (6): Binary Tree Traversal & Construction

Binary trees are a cornerstone of algorithm interviews, appearing in problems ranging from basic traversal to complex construction challenges. Mastering binary tree techniques is essential for demonstrating algorithmic proficiency. This comprehensive guide systematically covers four traversal methods (preorder, inorder, postorder, level-order), explores both recursive and iterative implementations, and solves classic construction problems (building trees from preorder+inorder and postorder+inorder). We'll also analyze complexity, common pitfalls, optimization techniques, and variant extensions.

Series Navigation

📚 LeetCode Algorithm Masterclass Series (10 Parts):

1. Hash Tables (Two Sum, Longest Consecutive, Group Anagrams)
2. Two Pointers Techniques (Collision pointers, fast-slow, sliding window)
3. Linked List Operations (Reverse, cycle detection, merge)
4. Binary Tree Traversal & Recursion (Inorder/Preorder/Postorder, LCA)
5. → Binary Tree Traversal & Construction (Pre/In/Post/Level-order, Construction) ← You are here
6. Backtracking Algorithms (Permutations, combinations, pruning)
7. Dynamic Programming Intro (1D/2D DP, state transition)
8. Greedy Algorithms (Interval scheduling, jump game)
9. Graph Algorithms (BFS/DFS, topological sort, union-find)
10. Bit Manipulation & Math (Bitwise tricks, math problems)

---

Binary Tree Fundamentals

What is a Binary Tree?

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

Key Properties:

• Each node has at most two children
• Left and right subtrees are ordered (cannot be swapped arbitrarily)
• An empty tree is also a binary tree

Basic Structure:

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

Types of Binary Trees

Complete Binary Tree: All levels are completely filled except possibly the last level, which is filled from left to right.

Full Binary Tree: Every node has either 0 or 2 children.

Binary Search Tree (BST): For each node, all values in the left subtree < node value < all values in the right subtree.

Balanced Binary Tree: The height difference between left and right subtrees is at most 1.

---

LeetCode 144: Binary Tree Preorder Traversal

Problem Statement

Given the root of a binary tree, return the preorder traversal of its nodes' values.

Preorder Order: Root → Left subtree → Right subtree

Example:

• Input: root = [1,null,2,3]
• Output: [1,2,3]

Constraints:

• The number of nodes in the tree is in the range [0, 100]
• -100 <= Node.val <= 100

Problem Analysis

Preorder traversal follows the pattern: visit the root first, then recursively process the left subtree, and finally the right subtree. This is the most intuitive traversal because you always see the root value first.

Use Cases:

• Printing directory structures (print current directory, then subdirectories)
• Copying binary trees (create root first, then copy subtrees)
• Expression tree evaluation (process operator before operands)

Solution Approach

Recursive Approach: Directly implement the definition — visit root, recurse left, recurse right.

Iterative Approach: Use a stack to simulate recursion. Push root onto stack, then loop: pop and visit, push right child first, then left child (order matters because stack is LIFO).

Complexity Analysis

• Time Complexity: , visiting each node once
• Space Complexity:
  • Recursive:, whereis tree height (recursion stack depth)
  • Iterative:, maximum stack depth equals tree height

Recursive Implementation

from typing import List, Optional

class Solution:
    def preorderTraversal(self, root: Optional[TreeNode]) -> List[int]:
        """
        Preorder traversal: Root -> Left -> Right
        
        Algorithm Steps:
        1. If root is None, return empty list
        2. Visit root node (add to result)
        3. Recursively traverse left subtree
        4. Recursively traverse right subtree
        
        Boundary Conditions:
        - Empty tree: return []
        - Single node: return [val]
        
        Variable Meanings:
        - root: root of current subtree
        - result: list storing traversal results
        """
        result = []
        
        def preorder(node):
            # Boundary: empty node returns immediately
            if not node:
                return
            
            # Step 1: Visit root node
            result.append(node.val)
            
            # Step 2: Recursively traverse left subtree
            preorder(node.left)
            
            # Step 3: Recursively traverse right subtree
            preorder(node.right)
        
        preorder(root)
        return result

Algorithm Principle:

Preorder traversal follows "root-left-right" order. The recursive implementation leverages the function call stack — after finishing the left subtree, execution automatically returns to the previous level to process the right subtree.

Execution Example (tree [1, null, 2, 3]):

Visit node 1 -> result = [1]
  Recurse left subtree (null) -> return immediately
  Recurse right subtree (node 2)
    Visit node 2 -> result = [1, 2]
      Recurse left subtree (node 3)
        Visit node 3 -> result = [1, 2, 3]
          Recurse left subtree (null)
          Recurse right subtree (null)
      Recurse right subtree (null)

Iterative Implementation

def preorderTraversal(self, root: Optional[TreeNode]) -> List[int]:
    """
    Iterative implementation: Use stack to simulate recursion
    
    Algorithm Steps:
    1. Initialize stack, push root
    2. While stack is not empty:
       a. Pop top node and visit
       b. If right child exists, push it
       c. If left child exists, push it
    3. Return result
    
    Key Technique:
    - Push right child first, then left child (stack is LIFO)
    - This ensures "root-left-right" order when popping
    
    Boundary Conditions:
    - Empty tree: stack empty, return []
    """
    if not root:
        return []
    
    result = []
    stack = [root]  # Initialize stack
    
    while stack:
        # Pop top node
        node = stack.pop()
        result.append(node.val)  # Visit root node
        
        # Push right first, then left
        # Popping order: left -> right (matches preorder)
        if node.right:
            stack.append(node.right)
        if node.left:
            stack.append(node.left)
    
    return result

Why Push Right Before Left:

Stacks are Last-In-First-Out (LIFO). To visit the left subtree first, we need the left child to be pushed last, so it pops first.

Execution Example (tree [1, null, 2, 3]):

Initial: stack = [1], result = []
Iteration 1: Pop 1 -> result = [1]
             Push 2 (right) -> stack = [2]
             Push null (left, skip)
Iteration 2: Pop 2 -> result = [1, 2]
             Push null (right, skip)
             Push 3 (left) -> stack = [3]
Iteration 3: Pop 3 -> result = [1, 2, 3]
             Push null (right, skip)
             Push null (left, skip)
Iteration 4: stack empty, end

Common Pitfalls

Pitfall 1: Forgetting to Handle Null Nodes

# ❌ Wrong
def preorder(node):
    result.append(node.val)  # Error if node is None
    preorder(node.left)
    preorder(node.right)

# ✅ Correct
def preorder(node):
    if not node:
        return
    result.append(node.val)
    preorder(node.left)
    preorder(node.right)

Pitfall 2: Wrong Push Order in Iterative Implementation

# ❌ Wrong: Push left then right
if node.left:
    stack.append(node.left)
if node.right:
    stack.append(node.right)
# This visits right subtree first, order becomes "root-right-left"

# ✅ Correct: Push right then left
if node.right:
    stack.append(node.right)
if node.left:
    stack.append(node.left)

Variant Extension

Variant 1: Morris Preorder Traversal (Space)

Morris traversal uses null pointers in the tree to achievespace complexity:

def preorderTraversal_morris(self, root: Optional[TreeNode]) -> List[int]:
    """
    Morris preorder traversal: O(1) space complexity
    
    Core Idea: Use null pointers of leaf nodes to create temporary links
    After visiting left subtree, return to root via this link
    """
    result = []
    current = root
    
    while current:
        if not current.left:
            # No left subtree, visit current node directly
            result.append(current.val)
            current = current.right
        else:
            # Find rightmost node in left subtree (predecessor)
            predecessor = current.left
            while predecessor.right and predecessor.right != current:
                predecessor = predecessor.right
            
            if not predecessor.right:
                # Create temporary link
                result.append(current.val)  # Visit root
                predecessor.right = current
                current = current.left
            else:
                # Temporary link exists, left subtree already visited
                predecessor.right = None  # Restore tree structure
                current = current.right
    
    return result

Complexity Analysis:

• Time Complexity:, each node visited at most twice
• Space Complexity:, only constant extra space

---

LeetCode 94: Binary Tree Inorder Traversal

Problem Statement

Given the root of a binary tree, return the inorder traversal of its nodes' values.

Inorder Order: Left subtree → Root → Right subtree

Example:

• Input: root = [1,null,2,3]
• Output: [1,3,2]

Problem Analysis

Inorder traversal processes left subtree first, then root, then right subtree. For Binary Search Trees (BST), inorder traversal produces a sorted sequence.

Use Cases:

• BST sorted output: Inorder traversal of BST gives ascending order
• Expression tree evaluation: Inorder traversal of expression tree gives infix expression
• BST validation: Check if inorder result is sorted

Solution Approach

Recursive Approach: Recurse left, visit root, recurse right.

Iterative Approach: Use stack to simulate recursion. Start from root, go left all the way, pushing nodes onto stack. Then pop and visit, turn to right subtree, repeat.

Complexity Analysis

• Time Complexity:
• Space Complexity:, whereis tree height

Recursive Implementation

def inorderTraversal(self, root: Optional[TreeNode]) -> List[int]:
    """
    Inorder traversal: Left -> Root -> Right
    
    Algorithm Steps:
    1. Recursively traverse left subtree
    2. Visit root node
    3. Recursively traverse right subtree
    """
    result = []
    
    def inorder(node):
        if not node:
            return
        
        inorder(node.left)      # Process left subtree first
        result.append(node.val)  # Then visit root
        inorder(node.right)     # Finally process right subtree
    
    inorder(root)
    return result

Iterative Implementation

def inorderTraversal(self, root: Optional[TreeNode]) -> List[int]:
    """
    Iterative implementation: Use stack to simulate recursion
    
    Algorithm Steps:
    1. Start from root, go left all the way, push nodes onto stack
    2. Pop top node and visit
    3. Turn to right subtree, repeat step 1
    
    Key Technique:
    - Use current pointer to track current node
    - When current is None and stack is empty, traversal ends
    """
    result = []
    stack = []
    current = root
    
    while current or stack:
        # Go left all the way
        while current:
            stack.append(current)
            current = current.left
        
        # Pop top node (leftmost node)
        current = stack.pop()
        result.append(current.val)  # Visit node
        
        # Turn to right subtree
        current = current.right
    
    return result

Execution Example (tree [1, null, 2, 3]):

Initial: current = 1, stack = [], result = []
Iteration 1: current = 1, go left all the way
             Push 1 -> stack = [1]
             current = null
             Pop 1 -> result = [1]
             current = 2 (right child of 1)
Iteration 2: current = 2, go left all the way
             Push 2 -> stack = [2]
             current = 3 (left child of 2)
             Push 3 -> stack = [2, 3]
             current = null
             Pop 3 -> result = [1, 3]
             current = null (right child of 3)
             Pop 2 -> result = [1, 3, 2]
             current = null (right child of 2)
Iteration 3: current = null, stack = [], end

Common Pitfall

Pitfall: Forgetting to Turn to Right Subtree

# ❌ Wrong
while current or stack:
    while current:
        stack.append(current)
        current = current.left
    current = stack.pop()
    result.append(current.val)
    # Missing: current = current.right
    # Causes infinite loop

# ✅ Correct
while current or stack:
    while current:
        stack.append(current)
        current = current.left
    current = stack.pop()
    result.append(current.val)
    current = current.right  # Must turn to right subtree

---

LeetCode 145: Binary Tree Postorder Traversal

Problem Statement

Given the root of a binary tree, return the postorder traversal of its nodes' values.

Postorder Order: Left subtree → Right subtree → Root

Example:

• Input: root = [1,null,2,3]
• Output: [3,2,1]

Problem Analysis

Postorder traversal processes left and right subtrees first, then visits root. This order is useful when deleting tree nodes, as you need to delete children before parent.

Use Cases:

• Deleting binary tree: Delete subtrees first, then root
• Calculating directory size: Calculate subdirectory sizes first, then total
• Expression tree evaluation: Postorder traversal gives postfix expression (Reverse Polish Notation)

Solution Approach

Recursive Approach: Recurse left, recurse right, visit root.

Iterative Approach: Postorder iteration is more complex. Method 1: Use two stacks, push in "root-right-left" order to stack1, then pop all to stack2, finally pop stack2 to get "left-right-root". Method 2: Use one stack, track visit state for each node (unvisited, left visited, right visited).

Complexity Analysis

• Time Complexity:
• Space Complexity:

Recursive Implementation

def postorderTraversal(self, root: Optional[TreeNode]) -> List[int]:
    """
    Postorder traversal: Left -> Right -> Root
    
    Algorithm Steps:
    1. Recursively traverse left subtree
    2. Recursively traverse right subtree
    3. Visit root node
    """
    result = []
    
    def postorder(node):
        if not node:
            return
        
        postorder(node.left)     # Process left subtree first
        postorder(node.right)    # Then process right subtree
        result.append(node.val)  # Finally visit root
    
    postorder(root)
    return result

Iterative Implementation (Two-Stack Method)

def postorderTraversal(self, root: Optional[TreeNode]) -> List[int]:
    """
    Iterative implementation: Use two stacks
    
    Algorithm Steps:
    1. Use stack1 to traverse in "root-right-left" order
    2. Push popped nodes from stack1 to stack2
    3. Pop stack2 sequentially to get "left-right-root" order
    
    Key Technique:
    - Stack1: root -> right -> left (mirror of preorder)
    - Stack2: Reverse to get left -> right -> root (postorder)
    """
    if not root:
        return []
    
    stack1 = [root]
    stack2 = []
    
    while stack1:
        node = stack1.pop()
        stack2.append(node)  # Push to stack2
        
        # Push left first, then right (so stack2 pops right->left, reversed to left->right)
        if node.left:
            stack1.append(node.left)
        if node.right:
            stack1.append(node.right)
    
    # Pop stack2 sequentially
    result = []
    while stack2:
        result.append(stack2.pop().val)
    
    return result

Why Two-Stack Method Works:

Stack1 traverses in "root-right-left" order (mirror of preorder), pushing to stack2 maintains this order. Popping stack2 reverses it to "left-right-root" (postorder).

Iterative Implementation (Single-Stack Method)

def postorderTraversal(self, root: Optional[TreeNode]) -> List[int]:
    """
    Iterative implementation: Use one stack, track visit state
    
    Algorithm Steps:
    1. Use stack to store (node, state) tuples
    2. State: 0=unvisited, 1=left visited, 2=right visited
    3. Decide next step based on state
    """
    if not root:
        return []
    
    result = []
    stack = [(root, 0)]  # (node, state)
    
    while stack:
        node, state = stack.pop()
        
        if state == 0:
            # Unvisited: visit left subtree first
            stack.append((node, 1))  # Mark as left visited
            if node.left:
                stack.append((node.left, 0))
        elif state == 1:
            # Left visited: visit right subtree
            stack.append((node, 2))  # Mark as right visited
            if node.right:
                stack.append((node.right, 0))
        else:
            # Right visited: visit root node
            result.append(node.val)
    
    return result

Algorithm Visualization: The animation below demonstrates postorder traversal visiting nodes in "left-right-root" order:

---

LeetCode 102: Binary Tree Level Order Traversal

Problem Statement

Given the root of a binary tree, return the level order traversal of its nodes' values (i.e., from left to right, level by level).

Example:

• Input: root = [3,9,20,null,null,15,7]
• Output: [[3],[9,20],[15,7]]

Problem Analysis

Level-order traversal (BFS) visits nodes level by level from top to bottom, left to right. Requires a queue (FIFO) to maintain order.

Use Cases:

• Printing binary tree: Print tree structure by level
• Finding shortest path: Find shortest path from root to leaf
• Serializing binary tree: Serialize tree structure by level

Solution Approach

Use queue to implement BFS. Enqueue root, then loop: record current level size, dequeue these nodes and visit, enqueue their children.

Complexity Analysis

• Time Complexity:, each node visited once
• Space Complexity:, whereis maximum tree width (maximum queue length)

Implementation

from collections import deque

def levelOrder(self, root: Optional[TreeNode]) -> List[List[int]]:
    """
    Level-order traversal: Use queue to implement BFS
    
    Algorithm Steps:
    1. Enqueue root node
    2. While queue is not empty:
       a. Record current level size (queue length)
       b. Dequeue these nodes, visit and collect to current level result
       c. Enqueue children of dequeued nodes
    3. Return results of all levels
    
    Key Technique:
    - Use level_size to record nodes per level, ensure level-by-level processing
    - Children enqueued processed in next iteration
    """
    if not root:
        return []
    
    result = []
    queue = deque([root])
    
    while queue:
        level_size = len(queue)  # Number of nodes in current level
        level = []  # Current level result
        
        # Process all nodes in current level
        for _ in range(level_size):
            node = queue.popleft()
            level.append(node.val)
            
            # Enqueue children (next level)
            if node.left:
                queue.append(node.left)
            if node.right:
                queue.append(node.right)
        
        result.append(level)
    
    return result

Execution Example (tree [3,9,20,null,null,15,7]):

Initial: queue = [3], result = []
Level 1: level_size = 1
         Dequeue 3 -> level = [3]
         Enqueue 9, 20 -> queue = [9, 20]
         result = [[3]]
Level 2: level_size = 2
         Dequeue 9 -> level = [9]
         Dequeue 20 -> level = [9, 20]
         Enqueue 15, 7 -> queue = [15, 7]
         result = [[3], [9, 20]]
Level 3: level_size = 2
         Dequeue 15 -> level = [15]
         Dequeue 7 -> level = [15, 7]
         No children to enqueue
         result = [[3], [9, 20], [15, 7]]
End: queue empty

Algorithm Visualization: The animation below demonstrates level-order traversal visiting nodes level by level:

Common Pitfall

Pitfall: Forgetting to Record Level Size

# ❌ Wrong
while queue:
    node = queue.popleft()
    result.append(node.val)  # No level separation, all nodes mixed
    if node.left:
        queue.append(node.left)
    if node.right:
        queue.append(node.right)

# ✅ Correct
while queue:
    level_size = len(queue)  # Must record level size
    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)

---

LeetCode 105: Construct Binary Tree from Preorder and Inorder Traversal

Problem Statement

Given two integer arrays preorder and inorder where preorder is the preorder traversal of a binary tree and inorder is the inorder traversal of the same tree, construct and return the binary tree.

Example:

• Input: preorder = [3,9,20,15,7], inorder = [9,3,15,20,7]
• Output: [3,9,20,null,null,15,7]

Constraints:

- - - - preorder and inorder consist of unique values

Problem Analysis

Core Insight:

1. First element of preorder is the root
2. Find root in inorder, left side is left subtree, right side is right subtree
3. Recursively construct left and right subtrees

Key Steps:

1. Take first element from preorder as root
2. Find root position in inorder
3. Based on root position, determine left and right subtree ranges
4. Recursively construct left and right subtrees

Solution Approach

Use recursion + hash map to optimize lookup. Hash map stores index of each value in inorder, avoiding linear search each time.

Complexity Analysis

• Time Complexity:, each node visited once, hash map lookup
• Space Complexity:, hash map+ recursion stack

Implementation

def buildTree(self, preorder: List[int], inorder: List[int]) -> Optional[TreeNode]:
    """
    Construct binary tree from preorder and inorder traversal
    
    Algorithm Steps:
    1. Create hash map storing index of each value in inorder
    2. Recursive function build(pre_start, pre_end, in_start, in_end):
       a. If pre_start > pre_end, return None
       b. Take preorder[pre_start] as root value
       c. Find root position root_idx in inorder
       d. Calculate left subtree size: left_size = root_idx - in_start
       e. Recursively construct left subtree: build(pre_start+1, pre_start+left_size, in_start, root_idx-1)
       f. Recursively construct right subtree: build(pre_start+left_size+1, pre_end, root_idx+1, in_end)
    
    Boundary Conditions:
    - Empty array: pre_start > pre_end
    - Single node: pre_start == pre_end
    
    Optimization Technique:
    - Use hash map to store inorder indices, avoid linear search each time
    """
    # Create hash map: value -> index
    inorder_map = {val: idx for idx, val in enumerate(inorder)}
    
    def build(pre_start, pre_end, in_start, in_end):
        # Boundary: empty subtree
        if pre_start > pre_end:
            return None
        
        # Root value
        root_val = preorder[pre_start]
        root = TreeNode(root_val)
        
        # Find root position in inorder
        root_idx = inorder_map[root_val]
        
        # Calculate left subtree size
        left_size = root_idx - in_start
        
        # Recursively construct left subtree
        # Preorder: pre_start+1 to pre_start+left_size
        # Inorder: in_start to root_idx-1
        root.left = build(
            pre_start + 1,
            pre_start + left_size,
            in_start,
            root_idx - 1
        )
        
        # Recursively construct right subtree
        # Preorder: pre_start+left_size+1 to pre_end
        # Inorder: root_idx+1 to in_end
        root.right = build(
            pre_start + left_size + 1,
            pre_end,
            root_idx + 1,
            in_end
        )
        
        return root
    
    return build(0, len(preorder) - 1, 0, len(inorder) - 1)

Index Calculation Details:

Assume preorder = [3,9,20,15,7], inorder = [9,3,15,20,7]:

Root: 3 (preorder[0])
Position in inorder: index=1

Left subtree:
  - Preorder range: [9] (preorder[1:1+1])
  - Inorder range: [9] (inorder[0:1])
  
Right subtree:
  - Preorder range: [20,15,7] (preorder[2:5])
  - Inorder range: [15,20,7] (inorder[2:5])

Algorithm Principle

Why Binary Tree is Uniquely Determined:

Preorder tells us root position, inorder tells us left-right subtree division. Combining these uniquely determines tree structure.

Mathematical Proof:

For a tree withnodes, there arepossible preorder traversals andpossible inorder traversals. But given preorder and inorder, tree structure is unique (assuming no duplicate values).

Common Pitfalls

Pitfall 1: Wrong Index Calculation

# ❌ Wrong: Incorrect left subtree size
left_size = root_idx  # Should be root_idx - in_start

# ✅ Correct
left_size = root_idx - in_start

Pitfall 2: Forgetting Boundary Conditions

# ❌ Wrong
def build(pre_start, pre_end, in_start, in_end):
    root_val = preorder[pre_start]  # Index out of bounds if pre_start > pre_end
    
# ✅ Correct
def build(pre_start, pre_end, in_start, in_end):
    if pre_start > pre_end:
        return None
    root_val = preorder[pre_start]

---

LeetCode 106: Construct Binary Tree from Inorder and Postorder Traversal

Problem Statement

Given two integer arrays inorder and postorder where inorder is the inorder traversal of a binary tree and postorder is the postorder traversal of the same tree, construct and return the binary tree.

Example:

• Input: inorder = [9,3,15,20,7], postorder = [9,15,7,20,3]
• Output: [3,9,20,null,null,15,7]

Problem Analysis

Core Insight:

1. Last element of postorder is the root
2. Find root in inorder, left side is left subtree, right side is right subtree
3. Recursively construct left and right subtrees

Difference from preorder construction: root is at the end of postorder, not the beginning.

Solution Approach

Similar to preorder+inorder construction, but root taken from end of postorder, right subtree range calculated from right to left.

Complexity Analysis

• Time Complexity:
• Space Complexity:

Implementation

def buildTree(self, inorder: List[int], postorder: List[int]) -> Optional[TreeNode]:
    """
    Construct binary tree from postorder and inorder traversal
    
    Algorithm Steps:
    1. Create hash map storing inorder indices
    2. Recursive function build(in_start, in_end, post_start, post_end):
       a. If post_start > post_end, return None
       b. Take postorder[post_end] as root value
       c. Find root position root_idx in inorder
       d. Calculate right subtree size: right_size = in_end - root_idx
       e. Recursively construct left and right subtrees
    
    Key Difference:
    - Root at end of postorder (post_end)
    - Right subtree range calculated from right to left
    """
    inorder_map = {val: idx for idx, val in enumerate(inorder)}
    
    def build(in_start, in_end, post_start, post_end):
        if post_start > post_end:
            return None
        
        # Root value (last in postorder)
        root_val = postorder[post_end]
        root = TreeNode(root_val)
        
        # Find root position in inorder
        root_idx = inorder_map[root_val]
        
        # Calculate right subtree size
        right_size = in_end - root_idx
        
        # Recursively construct left subtree
        # Inorder: in_start to root_idx-1
        # Postorder: post_start to post_end-right_size-1
        root.left = build(
            in_start,
            root_idx - 1,
            post_start,
            post_end - right_size - 1
        )
        
        # Recursively construct right subtree
        # Inorder: root_idx+1 to in_end
        # Postorder: post_end-right_size to post_end-1
        root.right = build(
            root_idx + 1,
            in_end,
            post_end - right_size,
            post_end - 1
        )
        
        return root
    
    return build(0, len(inorder) - 1, 0, len(postorder) - 1)

---

Traversal Methods Comparison

Traversal	Order	Recursive Difficulty	Iterative Difficulty	Typical Applications
Preorder	Root-Left-Right	⭐	⭐⭐	Copy tree, print directory
Inorder	Left-Root-Right	⭐	⭐⭐	BST sorted output, validate BST
Postorder	Left-Right-Root	⭐	⭐⭐⭐	Delete tree, calculate directory size
Level-order	Top-bottom, left-right	⭐⭐	⭐⭐	Print tree, find shortest path

Memory Mnemonic:

• Preorder: Root first (Root-Left-Right)
• Inorder: Root middle (Left-Root-Right)
• Postorder: Root last (Left-Right-Root)
• Level-order: Level by level (BFS)

---

Q&A: Common Questions About Binary Tree Traversal

Q1: Why Does Inorder Traversal of BST Produce Sorted Sequence?

A: BST definition: For each node, all values in left subtree < node value < all values in right subtree.

Inorder traversal order is "left-root-right", meaning: 1. First visit all values less than current node (left subtree) 2. Then visit current node 3. Finally visit all values greater than current node (right subtree)

Therefore, inorder traversal of BST naturally produces ascending sequence.

Verification:

# BST: [4,2,6,1,3,5,7]
# Inorder: [1,2,3,4,5,6,7] ✅ Sorted

---

Q2: Which is Better: Iterative or Recursive Implementation?

A: Each has pros and cons:

Aspect	Recursive	Iterative
Code Simplicity	✅ Simpler	❌ More complex
Space Complexity	❌(recursion stack)	✅(explicit stack)
Stack Overflow Risk	❌ May overflow at great depth	✅ Controllable
Understanding Difficulty	✅ Intuitive	❌ Need to understand stack operations
Performance	Comparable	Comparable

Recommendation:

• Interview: Prefer recursion (simpler), rewrite to iterative if interviewer requests
• Production: Use recursion when depth is controllable, use iterative when depth is very large
• Learning: Master both, understand the essence

---

Q3: How to Choose Traversal Method?

A: Choose based on problem requirements:

Preorder suitable for: - Need to process root before subtrees - Copy tree structure - Print directory structure

Inorder suitable for: - BST operations (search, validate, sorted output) - Expression tree infix expression

Postorder suitable for: - Need to process subtrees before root - Delete tree nodes - Calculate directory size - Expression tree postfix expression

Level-order suitable for: - Need level-by-level processing - Find shortest path - Serialize binary tree

---

Q4: What are the Advantages of Morris Traversal?

A: Main advantage is space complexity.

Comparison:

Method	Space Complexity	Time Complexity	Use Cases
Recursive			General cases
Iterative + Stack			General cases
Morris			Space-constrained

Costs:

• Higher code complexity
• Modifies tree structure (temporary links)
• Not suitable for multi-threaded environments

Recommendation: Unless space is strictly limited, prefer recursive or iterative implementation.

---

Q5: Why Do We Need Inorder Traversal to Construct Binary Tree?

A: Inorder traversal provides left-right subtree division information.

Why Preorder + Postorder Cannot Uniquely Determine:

Consider two different trees:

Tree 1:     1          Tree 2:     1
          /                        \
         2                          2

• Preorder both: [1, 2]
• Postorder both: [2, 1]
• But tree structures differ!

Why Preorder + Inorder Can Uniquely Determine:

• Preorder tells us root position
• Inorder tells us left-right subtree division
• Combining both uniquely determines structure

Mathematical Proof: Fornodes, given preorder and inorder, tree structure is unique (when node values are unique).

---

Q6: How to Handle Binary Trees with Duplicate Values?

A: With duplicate values, construction may not be unique.

Problem: If preorder = [1,1,1], inorder = [1,1,1], cannot uniquely determine tree structure.

Solutions:

1. Assume constraint: Problems usually guarantee unique node values
2. If duplicates allowed: Need additional information (e.g., node ID) to distinguish
3. Practical application: Usually distinguish by node references rather than values

---

Q7: Why is Level-Order Traversal Time Complexity?

A: Each node is enqueued once and dequeued once.

Analysis:

• Enqueue operations:times (once per node)
• Dequeue operations:times (once per node)
• Visit operations:times (once per node)

Total operations: Space Complexity: Maximum queue length is maximum tree width, usually, worst case (complete binary tree).

---

Summary: Key Points of Binary Tree Traversal

Memory Formulas:

• Preorder: Root → Left → Right
• Inorder: Left → Root → Right
• Postorder: Left → Right → Root
• Level-order: BFS, level by level

Memory Mnemonic:

Pre/In/Post determined by root position, Level-order is BFS

Tree construction needs inorder, left-right division depends on it

Practical Checklist:

• Master recursive implementation of four traversals
• Master iterative implementation of preorder, inorder, level-order
• Understand two methods for postorder iterative implementation
• Master constructing binary tree from preorder+inorder
• Master constructing binary tree from postorder+inorder
• Understand Morris traversal principle (optional)
• Able to choose appropriate traversal method based on problem

Common Mistakes to Avoid:

• ✅ Check null nodes in recursion
• ✅ Pay attention to push order in iteration
• ✅ Record level size in level-order traversal
• ✅ Correctly calculate index ranges when constructing tree

By systematically mastering binary tree traversal and construction, you can solve most binary tree-related LeetCode problems. Remember: Recursion is the foundation, iteration is advanced, understanding the essence is key!