Preorder Traversal

1. 1.Binary Tree Preorder Traversal
   Root -> Left -> Right: process node value before recursing left & right subtreeseasy
2. 2.N-ary Tree Preorder Traversal
   Process node value then iterate for _, child := range node.Childreneasy
3. 3.Flatten Binary Tree to Linked List
   Preorder traversal order: rewire right pointers while maintaining left = nilmedium
4. 4.Serialize and Deserialize Binary Tree
   Preorder traversal with nil markers "#" (e.g. 1,2,#,#,3,#,#)hard
5. 5.Construct Binary Tree from Preorder and Inorder Traversal
   Preorder first value = root; Inorder index splits left & right subtreesmedium
6. 6.Construct BST from Preorder Traversal
   First value = root; pass upper bound down recursion or use stackmedium
7. 7.Binary Tree Paths
   Preorder DFS carrying current string path downward to leaveseasy
8. 8.Path Sum
   Preorder DFS carrying targetSum - node.Val downward to leaf nodeseasy
9. 9.Path Sum II
   Preorder DFS + Backtracking: append node -> recurse subtrees -> remove nodemedium
10. 10.Count Good Nodes in Binary Tree
    Preorder DFS carrying maxValSeen downward to childrenmedium
11. 11.Sum Root to Leaf Numbers
    Preorder DFS carrying current number accumulator (curr * 10 + node.Val) downwardmedium
12. 12.Maximum Difference Between Node and Ancestor
    Preorder DFS carrying minVal & maxVal seen so far downward to leavesmedium
13. 13.Copy / Clone Tree
    Preorder traversal instantiating new TreeNode(root.Val) before childrenmedium
14. 14.Subtree Traversal Problems
    Preorder check: isSameTree(node, subRoot) || isSubtree(node.Left) || isSubtree(node.Right)easy

1. 15.Recover a Tree From Preorder Traversal
   Parse depth dashes "-" in preorder string using monotonic stackhard
2. 16.Verify Preorder Serialization of a Binary Tree
   Degree counting: initial slot = 1, non-null node consumes 1 slot & adds 2 slotsmedium
3. 17.Verify Preorder Sequence in BST
   Monotonic stack tracking min lower bound as you move rightmedium
4. 18.Boundary Traversal
   Preorder for left boundary -> leaves -> right boundary bottom-upmedium
5. 19.Root-to-Leaf Path Problems
   Preorder DFS passing parent context downward to leaveseasy
6. 20.Flatten Multilevel Tree Variants
   Preorder flattening for doubly linked lists with child pointersmedium

How to Think

1. Need current node before children?Preorder Traversal (Root -> Left -> Right)
2. Need root-to-leaf path / context?Preorder DFS + carry state DOWNWARD
3. Need serialize tree shape?Preorder + nil markers "#"
4. Need flatten tree root-first?Preorder order
5. Need build tree from preorder?First value is ROOT!

type TreeNode struct {
    Val   int
    Left  *TreeNode
    Right *TreeNode
}

// 1. Recursive Preorder: Root -> Left -> Right
func preorderRecursive(root *TreeNode) []int {
    result := []int{}
    var dfs func(node *TreeNode)
    dfs = func(node *TreeNode) {
        if node == nil {
            return
        }
        result = append(result, node.Val) // Process Root First!
        dfs(node.Left)
        dfs(node.Right)
    }
    dfs(root)
    return result
}

// 2. Iterative Preorder: Explicit Stack LIFO (Push RIGHT first!)
func preorderIterative(root *TreeNode) []int {
    if root == nil {
        return nil
    }
    result := []int{}
    stack := []*TreeNode{root}

    for len(stack) > 0 {
        node := stack[len(stack)-1]
        stack = stack[:len(stack)-1]

        result = append(result, node.Val)

        // Push RIGHT first so LEFT is on top and pops first!
        if node.Right != nil {
            stack = append(stack, node.Right)
        }
        if node.Left != nil {
            stack = append(stack, node.Left)
        }
    }
    return result
}

Iterative Stack Rule: Push RIGHT First

Serialization & Rebuilding Trees from Preorder

Preorder        → ROOT -> LEFT -> RIGHT (Parent processed before children)
Iterative Stack → Push RIGHT first so LEFT pops first
State Flow      → Parent passes parameters DOWNWARD to children
Serialization   → Preorder + nil markers (#)
Tree Build      → Preorder first element = ROOT

Common Interview Mistakes

Interview Rules

1. 1. Root node processed first? → Preorder Traversal
2. 2. Traversal sequence? → ROOT -> LEFT -> RIGHT
3. 3. Root-to-leaf paths? → Preorder DFS carrying state DOWNWARD
4. 4. Iterative stack rule? → Push node.Right first, then node.Left
5. 5. Tree flattening? → Flattened order matches Preorder traversal order
6. 6. Tree serialization? → Preorder + nil markers (#)
7. 7. Tree reconstruction? → Preorder first element is ROOT
8. 8. Overall Complexity → Time: O(N) | Stack Space: O(H) (O(log N) balanced, O(N) skewed)

Preorder        → ROOT -> LEFT -> RIGHT
Root            → Process first
Path / State    → Pass downward
Recursive       → Node, Left, Right
Iterative Stack → Push RIGHT then LEFT
Flatten         → Preorder
Serialize       → Preorder + nil markers
Tree Build      → Preorder first val = ROOT
Time            → O(N)

💡 Golden Rule: "Process the parent first, then let that information flow down through the left and right subtrees."