Boundary Traversal of Binary Tree in DSA Typescript - Execution Trace

Concept Flow - Boundary Traversal of Binary Tree

Start at root

↓

Traverse left boundary

↓

Traverse leaf nodes

↓

Traverse right boundary bottom-up

↓

Combine all nodes for boundary traversal

The traversal collects nodes from the left edge top-down, then all leaves left to right, then the right edge bottom-up, combining them for the boundary.

Execution Sample

DSA Typescript

function boundaryTraversal(root: TreeNode | null): number[] {
  if (!root) return [];
  const result: number[] = [root.val];

  const isLeaf = (node: TreeNode | null): boolean => node !== null && node.left === null && node.right === null;

  // Traverse left boundary
  let curr: TreeNode | null = root.left;
  while (curr && (curr.left || curr.right)) {
    result.push(curr.val);
    curr = curr.left ? curr.left : curr.right;
  }

  // Traverse leaves
  const addLeaves = (node: TreeNode | null): void => {
    if (!node) return;
    if (isLeaf(node)) {
      result.push(node.val);
      return;
    }
    addLeaves(node.left);
    addLeaves(node.right);
  };
  addLeaves(root.left);
  addLeaves(root.right);

  // Traverse right boundary
  const rightStack: number[] = [];
  curr = root.right;
  while (curr && (curr.left || curr.right)) {
    rightStack.push(curr.val);
    curr = curr.right ? curr.right : curr.left;
  }
  while (rightStack.length) {
    result.push(rightStack.pop()!);
  }

  return result;
}

This code outlines the steps to collect boundary nodes of a binary tree in order.

Execution Table

Step	Operation	Node Visited	Pointer Changes	Tree State (Boundary Nodes Collected)
1	Start at root	1	root -> 1	[1]
2	Traverse left boundary	2	current -> 2	[1, 2]
3	Traverse left boundary	4	current -> 4	[1, 2, 4]
4	Traverse left boundary	null (leaf or no left/right child)	stop	[1, 2, 4]
5	Traverse leaf nodes	8	visit leaf	[1, 2, 4, 8]
6	Traverse leaf nodes	9	visit leaf	[1, 2, 4, 8, 9]
7	Traverse leaf nodes	5	visit leaf	[1, 2, 4, 8, 9, 5]
8	Traverse leaf nodes	6	visit leaf	[1, 2, 4, 8, 9, 5, 6]
9	Traverse right boundary bottom-up	3	stack push 3	[1, 2, 4, 8, 9, 5, 6]
10	Traverse right boundary bottom-up	7	stack push 7	[1, 2, 4, 8, 9, 5, 6]
11	Traverse right boundary bottom-up	null (no right/left child)	stop	[1, 2, 4, 8, 9, 5, 6]
12	Add right boundary nodes from stack	7	pop 7	[1, 2, 4, 8, 9, 5, 6, 7]
13	Add right boundary nodes from stack	3	pop 3	[1, 2, 4, 8, 9, 5, 6, 7, 3]
14	Traversal complete	null	end	[1, 2, 4, 8, 9, 5, 6, 7, 3]

💡 All boundary nodes collected: left boundary, leaves, right boundary bottom-up

Variable Tracker

Variable	Start	After Step 2	After Step 4	After Step 7	After Step 11	After Step 14
result	[]	[1, 2]	[1, 2, 4]	[1, 2, 4, 8, 9, 5, 6]	[1, 2, 4, 8, 9, 5, 6]	[1, 2, 4, 8, 9, 5, 6, 7, 3]
current (left boundary)	1	2	4	null	null	null
stack (right boundary)	[]	[]	[]	[]	[3,7]	[]

Key Moments - 3 Insights

Why do we not include leaf nodes when traversing the left and right boundaries?

Leaf nodes are collected separately in the leaf traversal step to avoid duplicates, as they can appear in both boundary and leaf traversals. See execution_table rows 5-8 for leaf collection.

Why is the right boundary collected bottom-up using a stack?

Right boundary nodes are added in reverse order to maintain correct traversal order. We push them while traversing down, then pop to add them bottom-up. See execution_table rows 9-13.

What happens if the tree has only one node?

The root is the only boundary node, so traversal ends after adding root. This is shown in execution_table row 1 and exit note.

Visual Quiz - 3 Questions

Look at the execution_table, what nodes are collected after step 7?

A [1, 2, 4, 8, 9, 5, 6]

B [1, 2, 4]

C [1, 2, 4, 8, 9]

D [1, 2, 4, 8, 9, 5]

💡 Hint

Check the 'Tree State' column at step 7 in execution_table.

At which step does the traversal start adding right boundary nodes to the result?

A Step 9

B Step 10

C Step 12

D Step 14

💡 Hint

Look for when nodes are popped from the stack in execution_table.

If the tree had no left child, how would the left boundary traversal steps change?

A Left boundary traversal would continue to leaves.

B Left boundary traversal would stop immediately after root.

C Left boundary traversal would add all nodes.

D Left boundary traversal would add right boundary nodes.

💡 Hint

Refer to variable_tracker for 'current (left boundary)' changes and execution_table steps 2-4.

Concept Snapshot

Boundary Traversal of Binary Tree:
- Start at root
- Traverse left boundary (excluding leaves) top-down
- Traverse all leaf nodes left to right
- Traverse right boundary (excluding leaves) bottom-up
- Combine all nodes in order
- Use stack for right boundary to reverse order

Full Transcript

Boundary traversal collects nodes around the edges of a binary tree. It starts at the root, then collects the left boundary nodes top-down excluding leaves, then all leaf nodes from left to right, and finally the right boundary nodes bottom-up excluding leaves. The right boundary is collected using a stack to reverse the order. This ensures no duplicates and correct traversal order. The final list combines these nodes to represent the boundary of the tree.