Left Side View of Binary Tree in DSA Typescript - Time & Space Complexity

Time Complexity: Left Side View of Binary Tree

O(n)

Understanding Time Complexity

We want to understand how the time needed to find the left side view of a binary tree changes as the tree grows.

How does the number of nodes affect the work done to get the left side view?

Scenario Under Consideration

Analyze the time complexity of the following code snippet.

function leftSideView(root: TreeNode | null): number[] {
  if (!root) return [];
  const result: number[] = [];
  const queue: (TreeNode | null)[] = [root];
  while (queue.length) {
    const levelSize = queue.length;
    for (let i = 0; i < levelSize; i++) {
      const node = queue.shift()!;
      if (i === 0) result.push(node.val);
      if (node.left) queue.push(node.left);
      if (node.right) queue.push(node.right);
    }
  }
  return result;
}
    

This code finds the left side view by visiting each level of the tree and recording the first node at each level.

Identify Repeating Operations

• Primary operation: The while loop runs once per level, and the inner for loop visits every node in the tree exactly once.
• How many times: Each node is processed once, so the total number of operations grows with the number of nodes n.

How Execution Grows With Input

As the number of nodes increases, the code visits each node once, so the work grows directly with the number of nodes.

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

Pattern observation: The operations increase linearly as the tree size grows.

Final Time Complexity

Time Complexity: O(n)

This means the time to find the left side view grows in direct proportion to the number of nodes in the tree.

Common Mistake

[X] Wrong: "Since we only take one node per level, the time complexity is O(height) or O(log n)."

[OK] Correct: Even though we record one node per level, we still visit every node to check their children, so the total work depends on all nodes, not just the levels.

Interview Connect

Understanding this helps you explain how breadth-first search visits nodes level by level, a common pattern in tree problems.

Self-Check

What if we changed the code to use recursion instead of a queue? How would the time complexity change?