Boundary Traversal of Binary Tree in DSA Typescript

Mental Model

We want to visit the outer edge nodes of a tree in a specific order: left edge top-down, leaves left to right, and right edge bottom-up.

Analogy: Imagine walking around the outside of a garden shaped like a tree, first along the left fence, then along the flowers at the bottom, and finally along the right fence going back up.

      1
     / \
    2   3
   / \   \
  4   5   6
     / \   \
    7   8   9

Left boundary: 1 -> 2 -> 4
Leaves: 4 -> 7 -> 8 -> 9
Right boundary: 3 -> 6 -> 9

Dry Run Walkthrough

Input: Binary tree: 1 with left child 2 and right child 3; 2 has children 4 and 5; 5 has children 7 and 8; 3 has right child 6; 6 has right child 9

Goal: Print boundary nodes in order: left boundary top-down, leaves left to right, right boundary bottom-up without duplicates

Step 1: Add root node 1 to boundary list

Boundary: [1]

Why: Root is always part of the boundary

Step 2: Traverse left boundary excluding leaves: add 2, then 4 (leaf, skip here)

Boundary: [1, 2]

Why: Left boundary nodes are added top-down excluding leaves to avoid duplicates

Step 3: Traverse leaves left to right: add 4, 7, 8, 9

Boundary: [1, 2, 4, 7, 8, 9]

Why: Leaves are added in left to right order to cover bottom edge

Step 4: Traverse right boundary excluding leaves bottom-up: add 6, then 3

Boundary: [1, 2, 4, 7, 8, 9, 6, 3]

Why: Right boundary nodes are added bottom-up excluding leaves to avoid duplicates

Result:

1 -> 2 -> 4 -> 7 -> 8 -> 9 -> 6 -> 3 -> null

Annotated Code

DSA Typescript

class TreeNode {
  val: number;
  left: TreeNode | null;
  right: TreeNode | null;
  constructor(val: number) {
    this.val = val;
    this.left = null;
    this.right = null;
  }
}

function isLeaf(node: TreeNode | null): boolean {
  return node !== null && node.left === null && node.right === null;
}

function addLeftBoundary(root: TreeNode | null, res: number[]): void {
  let curr = root?.left || null;
  while (curr !== null) {
    if (!isLeaf(curr)) res.push(curr.val); // add if not leaf
    if (curr.left !== null) curr = curr.left; // go left if possible
    else curr = curr.right; // else go right
  }
}

function addLeaves(root: TreeNode | null, res: number[]): void {
  if (root === null) return;
  if (isLeaf(root)) {
    res.push(root.val); // add leaf
    return;
  }
  addLeaves(root.left, res); // traverse left subtree
  addLeaves(root.right, res); // traverse right subtree
}

function addRightBoundary(root: TreeNode | null, res: number[]): void {
  let curr = root?.right || null;
  const temp: number[] = [];
  while (curr !== null) {
    if (!isLeaf(curr)) temp.push(curr.val); // add if not leaf
    if (curr.right !== null) curr = curr.right; // go right if possible
    else curr = curr.left; // else go left
  }
  for (let i = temp.length - 1; i >= 0; i--) {
    res.push(temp[i]); // add right boundary bottom-up
  }
}

function boundaryTraversal(root: TreeNode | null): number[] {
  const res: number[] = [];
  if (root === null) return res;
  res.push(root.val); // add root
  addLeftBoundary(root, res); // add left boundary
  addLeaves(root, res); // add leaves
  addRightBoundary(root, res); // add right boundary
  return res;
}

// Driver code
const root = new TreeNode(1);
root.left = new TreeNode(2);
root.right = new TreeNode(3);
root.left.left = new TreeNode(4);
root.left.right = new TreeNode(5);
root.left.right.left = new TreeNode(7);
root.left.right.right = new TreeNode(8);
root.right.right = new TreeNode(6);
root.right.right.right = new TreeNode(9);

const result = boundaryTraversal(root);
console.log(result.join(' -> ') + ' -> null');

res.push(root.val);

Add root to result

while (curr !== null) { if (!isLeaf(curr)) res.push(curr.val); if (curr.left !== null) curr = curr.left; else curr = curr.right; }

Traverse left boundary top-down excluding leaves

if (isLeaf(root)) { res.push(root.val); return; } addLeaves(root.left, res); addLeaves(root.right, res);

Add all leaf nodes left to right

while (curr !== null) { if (!isLeaf(curr)) temp.push(curr.val); if (curr.right !== null) curr = curr.right; else curr = curr.left; } for (let i = temp.length - 1; i >= 0; i--) { res.push(temp[i]); }

Traverse right boundary bottom-up excluding leaves

Output

1 -> 2 -> 4 -> 7 -> 8 -> 9 -> 6 -> 3 -> null

Complexity Analysis

Time: O(n) because we visit each node at most once during boundary traversal

Space: O(n) for the output list and recursion stack in worst case

vs Alternative: Compared to naive approach that might check all nodes multiple times, this method efficiently collects boundary nodes in a single traversal

Edge Cases

Empty tree

Returns empty list without error

DSA Typescript

if (root === null) return res;

Tree with only root node

Returns root node as boundary

DSA Typescript

res.push(root.val);

Tree with only left or only right subtree

Correctly returns boundary nodes without duplicates

DSA Typescript

while (curr !== null) { if (!isLeaf(curr)) res.push(curr.val); ... }

When to Use This Pattern

When asked to print or collect the outer nodes of a binary tree in a specific order, use boundary traversal to combine left edge, leaves, and right edge efficiently.

Common Mistakes

Mistake: Including leaf nodes twice by adding them in both boundary and leaf traversals
Fix: Exclude leaves from left and right boundary traversals and add them only once in leaf traversal

Summary

Prints the outer boundary nodes of a binary tree in a specific order.

Use when you need to list all edge nodes of a tree without duplicates.

The key is to separate left boundary, leaves, and right boundary to avoid repeats.

Practice

1. What is the main purpose of Boundary Traversal in a binary tree?

easy

A. To print all leaf nodes only

B. To print all nodes on the boundary in anti-clockwise direction

C. To print nodes level by level

D. To print nodes in in-order traversal

Solution

1. Step 1: Understand boundary traversal definition

   Boundary traversal prints nodes on the edges of the tree, including left boundary, leaves, and right boundary.

2. Step 2: Identify traversal direction

   The traversal is done in anti-clockwise direction starting from root, left boundary, leaves, then right boundary.

3. Final Answer:

   To print all nodes on the boundary in anti-clockwise direction -> Option B

4. Quick Check:

   Boundary traversal = anti-clockwise boundary nodes [OK]

Hint: Boundary traversal prints edges anti-clockwise [OK]

Common Mistakes:

• Confusing boundary traversal with leaf node traversal
• Thinking it prints nodes level-wise
• Assuming it prints in-order nodes

2. Which of the following TypeScript function signatures correctly represents a function to perform boundary traversal of a binary tree?

easy

A. function boundaryTraversal(): number[]

B. function boundaryTraversal(root: TreeNode): void

C. function boundaryTraversal(root: TreeNode, result: number[]): void

D. function boundaryTraversal(root: TreeNode): number[]

Solution

1. Step 1: Analyze function purpose

   The function should take the root node and return an array of numbers representing boundary nodes.

2. Step 2: Check signatures

   function boundaryTraversal(root: TreeNode): number[] takes root and returns number array, matching expected usage. function boundaryTraversal(root: TreeNode): void returns void, so no output. function boundaryTraversal(root: TreeNode, result: number[]): void requires external array input, less common. function boundaryTraversal(): number[] has no input, so invalid.

3. Final Answer:

   function boundaryTraversal(root: TreeNode): number[] -> Option D

4. Quick Check:

   Function returns boundary nodes array [OK]

Hint: Function should return array of boundary nodes [OK]

Common Mistakes:

• Using void return type without output
• Missing root parameter
• Expecting external array input unnecessarily

3. Given the binary tree below, what is the boundary traversal output?

      1
     / \
    2   3
   / \   \
  4   5   6
     / \  /
    7  8 9

medium

A. [1, 2, 4, 7, 8, 9, 6]

B. [1, 2, 4, 5, 7, 8, 9, 6, 3]

C. [1, 2, 4, 7, 8, 9, 6, 3]

D. [1, 2, 4, 7, 8, 9, 3, 6]

Solution

1. Step 1: Identify left boundary nodes

   Left boundary excluding leaves: 1, 2

2. Step 2: Identify leaf nodes left to right

   Leaves: 4, 7, 8, 9, 6

3. Step 3: Identify right boundary nodes bottom to top excluding leaves

   Right boundary: 3

4. Step 4: Combine in anti-clockwise order

   Boundary = left boundary + leaves (excluding duplicates) + right boundary = [1, 2, 4, 7, 8, 9, 6, 3]

5. Final Answer:

   [1, 2, 4, 7, 8, 9, 6, 3] -> Option C

6. Quick Check:

   Boundary traversal = [1,2,4,7,8,9,6,3] [OK]

Hint: Combine left boundary, leaves, right boundary anti-clockwise [OK]

Common Mistakes:

• Including leaf nodes twice
• Wrong order of right boundary nodes
• Missing root or boundary nodes

4. Consider the following TypeScript code snippet for boundary traversal. What is the bug?

function printBoundary(root: TreeNode | null) {
  if (!root) return;
  console.log(root.val);
  printLeftBoundary(root.left);
  printLeaves(root.left);
  printLeaves(root.right);
  printRightBoundary(root.right);
}

function printLeftBoundary(node: TreeNode | null) {
  if (!node || (!node.left && !node.right)) return;
  console.log(node.val);
  if (node.left) printLeftBoundary(node.left);
  else printLeftBoundary(node.right);
}

function printRightBoundary(node: TreeNode | null) {
  if (!node || (!node.left && !node.right)) return;
  if (node.right) printRightBoundary(node.right);
  else printRightBoundary(node.left);
  console.log(node.val);
}

medium

A. Left boundary includes leaf nodes which should be excluded

B. Root node is printed twice

C. Right boundary nodes are printed before recursive calls, causing wrong order

D. Leaves are printed twice because printLeaves is called on both left and right subtrees

Solution

1. Step 1: Analyze left boundary function

   printLeftBoundary prints node.val even if node is leaf, but leaves should be excluded from left boundary.

2. Step 2: Check leaf exclusion condition

   Condition (!node.left && !node.right) returns early, so leaves are excluded from printing in left boundary, so no bug here.

3. Step 3: Re-examine leaf printing calls

   printLeaves is called separately on left and right subtrees, so leaves are printed once only.

4. Step 4: Check right boundary printing order

   Right boundary prints after recursive calls, which is correct for bottom-up order.

5. Step 5: Identify actual bug

   Left boundary function prints node.val before recursive call, so leaf nodes on left boundary get printed twice: once in left boundary and once in leaves.

6. Final Answer:

   Left boundary includes leaf nodes which should be excluded -> Option A

7. Quick Check:

   Leaf nodes must not print in left boundary [OK]

Hint: Exclude leaves from left/right boundary printing [OK]

Common Mistakes:

• Printing leaves twice
• Printing right boundary in wrong order
• Printing root twice

5. You want to modify boundary traversal to print nodes in clockwise order starting from root. Which change is correct?

hard

A. Print root, then right boundary top-down, then leaves right to left, then left boundary bottom-up

B. Print root, then left boundary top-down, then leaves left to right, then right boundary bottom-up

C. Print root, then leaves left to right, then left boundary top-down, then right boundary bottom-up

D. Print root, then right boundary bottom-up, then leaves right to left, then left boundary top-down

Solution

1. Step 1: Understand clockwise boundary traversal order

   Clockwise traversal starts at root, then right boundary top-down, leaves right to left, then left boundary bottom-up.

2. Step 2: Match options with traversal order

   Print root, then right boundary top-down, then leaves right to left, then left boundary bottom-up matches this order exactly. Print root, then left boundary top-down, then leaves left to right, then right boundary bottom-up is anti-clockwise order. Options C and D mix orders incorrectly.

3. Final Answer:

   Print root, then right boundary top-down, then leaves right to left, then left boundary bottom-up -> Option A

4. Quick Check:

   Clockwise = root + right boundary + leaves + left boundary [OK]

Hint: Clockwise = root, right boundary, leaves, left boundary [OK]

Common Mistakes:

• Confusing clockwise with anti-clockwise order
• Printing boundaries in wrong direction
• Mixing leaf traversal order