Tree Traversal Preorder Root Left Right in DSA Go

Mental Model

Visit the root node first, then explore the left subtree, and finally the right subtree.

Analogy: Imagine reading a book: first you look at the title (root), then read the left page (left subtree), and then the right page (right subtree).

    1
   / \
  2   3
 / \
4   5

Dry Run Walkthrough

Input: Tree with nodes: 1 as root, 2 as left child, 3 as right child, 4 as left child of 2, 5 as right child of 2

Goal: Print nodes in preorder: root first, then left subtree, then right subtree

Step 1: Visit root node 1

Visited: 1

Why: Start traversal at the root

Step 2: Traverse left subtree starting at node 2

Visited: 1 -> 2

Why: After root, visit left subtree

Step 3: Traverse left subtree of node 2, visit node 4

Visited: 1 -> 2 -> 4

Why: Preorder visits root of subtree before children

Step 4: Back to node 2, traverse right subtree, visit node 5

Visited: 1 -> 2 -> 4 -> 5

Why: After left child, visit right child

Step 5: Back to root 1, traverse right subtree, visit node 3

Visited: 1 -> 2 -> 4 -> 5 -> 3

Why: After left subtree, visit right subtree

Result:

1 -> 2 -> 4 -> 5 -> 3 -> null

Annotated Code

DSA Go

package main

import "fmt"

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

func preorder(root *TreeNode) {
    if root == nil {
        return
    }
    fmt.Printf("%d -> ", root.Val) // visit root first
    preorder(root.Left)           // traverse left subtree
    preorder(root.Right)          // traverse right subtree
}

func main() {
    // Construct the tree:
    //     1
    //    / \
    //   2   3
    //  / \
    // 4   5
    root := &TreeNode{Val: 1}
    root.Left = &TreeNode{Val: 2}
    root.Right = &TreeNode{Val: 3}
    root.Left.Left = &TreeNode{Val: 4}
    root.Left.Right = &TreeNode{Val: 5}

    preorder(root)
    fmt.Print("null\n")
}

if root == nil { return }

stop traversal when reaching a leaf's child (nil)

fmt.Printf("%d -> ", root.Val) // visit root first

visit current node before children

preorder(root.Left) // traverse left subtree

recursively traverse left subtree

preorder(root.Right) // traverse right subtree

recursively traverse right subtree

Output

1 -> 2 -> 4 -> 5 -> 3 -> null

Complexity Analysis

Time: O(n) because each node is visited exactly once

Space: O(h) where h is the height of the tree due to recursion stack

vs Alternative: Compared to iterative traversal, recursive preorder is simpler but uses call stack; iterative uses explicit stack but can be more complex

Edge Cases

empty tree (root is nil)

function returns immediately without printing anything

DSA Go

if root == nil {
        return
    }

tree with single node

prints the single node value followed by null

DSA Go

if root == nil {
        return
    }

When to Use This Pattern

When you need to process the root node before its children in a tree, use preorder traversal to visit nodes in root-left-right order.

Common Mistakes

Mistake: Visiting left or right child before the root node
Fix: Print or process the root node value before recursive calls to left and right children

Summary

Visits the root node first, then recursively visits left and right subtrees.

Use when you want to process the root before its children, such as copying a tree or prefix expression evaluation.

The key insight is to handle the root node before diving into subtrees.