Boundary Traversal of Binary Tree in DSA Javascript - 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, how does the number of nodes affect the work done?

Scenario Under Consideration

Analyze the time complexity of the following code snippet.

function boundaryTraversal(root) {
  if (!root) return [];
  const result = [];
  function leftBoundary(node) {
    if (!node || (!node.left && !node.right)) return;
    result.push(node.val);
    if (node.left) leftBoundary(node.left);
    else leftBoundary(node.right);
  }
  function leaves(node) {
    if (!node) return;
    leaves(node.left);
    if (!node.left && !node.right) result.push(node.val);
    leaves(node.right);
  }
  function rightBoundary(node) {
    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 in the tree.
• How many times: The tree nodes are visited a constant number of times each (at most twice).

How Execution Grows With Input

As the number of nodes (n) increases, the total number of node visits is proportional to n, so the work grows linearly with n.

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

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

Final Time Complexity

Time Complexity: O(n)

This means the time to do the boundary traversal grows in direct proportion to the number of nodes in the tree.

Common Mistake

[X] Wrong: "The boundary traversal only visits boundary nodes, so it must be faster than visiting all nodes."

[OK] Correct: The code still visits many nodes to find leaves and edges, so it ends up visiting every node in the tree.

Interview Connect

Understanding how tree traversals scale helps you explain your approach clearly and shows you know how to handle data structures efficiently.

Self-Check

"What if we changed the code to use iterative traversal with stacks instead of recursion? How would the time complexity change?"