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.