Tree Traversal Preorder Root Left Right in DSA Go - Time & Space Complexity

Time Complexity: Tree Traversal Preorder Root Left Right

O(n)

Understanding Time Complexity

We want to understand how the time needed to visit all nodes in a tree grows as the tree gets bigger.

Specifically, we ask: How does preorder traversal scale with the number of nodes?

Scenario Under Consideration

Analyze the time complexity of the following code snippet.

func preorder(root *Node) {
    if root == nil {
        return
    }
    fmt.Println(root.value) // Visit root
    preorder(root.left)     // Traverse left subtree
    preorder(root.right)    // Traverse right subtree
}
    

This code visits each node starting from the root, then left child, then right child recursively.

Identify Repeating Operations

Identify the loops, recursion, array traversals that repeat.

• Primary operation: Visiting each node once (printing value).
• How many times: Exactly once per node in the tree.

How Execution Grows With Input

As the number of nodes grows, the number of visits grows at the same rate.

Input Size (n)	Approx. Operations
10	10 visits
100	100 visits
1000	1000 visits

Pattern observation: The operations grow linearly with the number of nodes.

Final Time Complexity

Time Complexity: O(n)

This means the time to complete preorder traversal grows directly in proportion to the number of nodes.

Common Mistake

[X] Wrong: "Preorder traversal takes more than linear time because it visits nodes multiple times."

[OK] Correct: Each node is visited exactly once, so the total work is proportional to the number of nodes, not more.

Interview Connect

Understanding preorder traversal time helps you explain how tree algorithms scale and shows you can analyze recursive code clearly.

Self-Check

"What if we changed preorder to inorder traversal? How would the time complexity change?"