Boundary Traversal of Binary Tree in DSA Go - Time & Space Complexity

Time Complexity: Boundary Traversal of Binary Tree

O(n)

Understanding Time Complexity

We want to understand how the time needed to do a boundary traversal of a binary tree changes as the tree grows.

Specifically, we ask: How many steps does it take to visit the boundary nodes of the tree?

Scenario Under Consideration

Analyze the time complexity of the following code snippet.

func boundaryTraversal(root *Node) []int {
    if root == nil {
        return []int{}
    }
    res := []int{root.data}
    addLeftBoundary(root.left, &res)
    addLeaves(root.left, &res)
    addLeaves(root.right, &res)
    addRightBoundary(root.right, &res)
    return res
}

// Helper functions traverse parts of the tree

This code collects the boundary nodes of a binary tree in anti-clockwise order.

Identify Repeating Operations

Identify the loops, recursion, array traversals that repeat.

• Primary operation: Traversing nodes in the left boundary, leaves, and right boundary.
• How many times: Each node is visited a constant number of times (at most twice) during these traversals.

How Execution Grows With Input

As the number of nodes (n) in the tree grows, the traversal visits each node a constant number of times.

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

Pattern observation: The number of steps grows roughly in direct proportion to the number of nodes.

Final Time Complexity

Time Complexity: O(n)

This means the time to do the boundary traversal grows linearly with the number of nodes in the tree.

Common Mistake

[X] Wrong: "Boundary traversal takes more than linear time because it does multiple traversals."

[OK] Correct: Although it looks like multiple passes, each node is visited only a constant number of times in total, so the overall time is still linear.

Interview Connect

Understanding this helps you explain how tree traversals work efficiently and shows you can analyze combined traversals clearly.

Self-Check

"What if the tree is skewed (like a linked list)? How would the time complexity change?"