Boundary Traversal of Binary Tree in DSA Typescript - 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.

The question is: how does the number of steps grow when the tree has more nodes?

Scenario Under Consideration

Analyze the time complexity of the following code snippet.

function boundaryTraversal(root: TreeNode | null): number[] {
  if (!root) return [];
  const result: number[] = [];
  function leftBoundary(node: TreeNode | null) {
    if (!node || (!node.left && !node.right)) return;
    result.push(node.val);
    if (node.left) leftBoundary(node.left);
    else leftBoundary(node.right);
  }
  function leaves(node: TreeNode | null) {
    if (!node) return;
    leaves(node.left);
    if (!node.left && !node.right) result.push(node.val);
    leaves(node.right);
  }
  function rightBoundary(node: TreeNode | null) {
    if (!node || (!node.left && !node.right)) return;
    if (node.right) rightBoundary(node.right);
    else rightBoundary(node.left);
    result.push(node.val);
  }
  result.push(root.val);
  leftBoundary(root.left);
  leaves(root.left);
  leaves(root.right);
  rightBoundary(root.right);
  return result;
}
    

This code collects the boundary nodes of a binary tree in order: left edge, leaves, then right edge.

Identify Repeating Operations

Identify the loops, recursion, array traversals that repeat.

• Primary operation: Recursive traversal of nodes to collect left boundary, leaves, and right boundary.
• How many times: Each node is visited at most once during these traversals.

How Execution Grows With Input

As the number of nodes in the tree increases, the code visits each node at most once to check if it belongs to the boundary.

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: "The boundary traversal only visits a few nodes, so it runs in constant time."

[OK] Correct: Even though only boundary nodes are collected, the code must check many nodes to find leaves and boundaries, so it still visits all nodes.

Interview Connect

Understanding this traversal helps you reason about tree algorithms and recursion, skills that are useful in many coding challenges and real projects.

Self-Check

"What if we changed the code to use an iterative approach with a stack instead of recursion? How would the time complexity change?"