Boundary Traversal of Binary Tree in DSA Javascript

Mental Model

We want to visit the outer edge nodes of a tree in a specific order: left edge, leaves, then right edge.

Analogy: Imagine walking around the outside of a park fence, first along the left side, then around the bottom (leaves), and finally up the right side, without stepping inside.

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

Boundary order: 1 -> 2 -> 4 -> 7 -> 8 -> 9 -> 6 -> 3 -> null

Dry Run Walkthrough

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

Goal: Print the boundary nodes in order: left boundary, leaves, right boundary (bottom-up)

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

Boundary: 1 -> 2

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

Step 3: Add all leaf nodes from left to right: 4, 7, 8, 9

Boundary: 1 -> 2 -> 4 -> 7 -> 8 -> 9

Why: Leaves are added after left boundary 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 edge nodes are added bottom-up to complete the boundary

Result:

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

Annotated Code

DSA Javascript

class Node {
  constructor(data) {
    this.data = data;
    this.left = null;
    this.right = null;
  }
}

function isLeaf(node) {
  return node.left === null && node.right === null;
}

function addLeftBoundary(root, boundary) {
  let curr = root.left;
  while (curr) {
    if (!isLeaf(curr)) boundary.push(curr.data); // add if not leaf
    if (curr.left) curr = curr.left; // go left if possible
    else curr = curr.right; // else go right
  }
}

function addLeaves(root, boundary) {
  if (root === null) return;
  if (isLeaf(root)) {
    boundary.push(root.data); // add leaf
    return;
  }
  addLeaves(root.left, boundary); // traverse left subtree
  addLeaves(root.right, boundary); // traverse right subtree
}

function addRightBoundary(root, boundary) {
  let curr = root.right;
  const stack = [];
  while (curr) {
    if (!isLeaf(curr)) stack.push(curr.data); // add if not leaf
    if (curr.right) curr = curr.right; // go right if possible
    else curr = curr.left; // else go left
  }
  while (stack.length > 0) {
    boundary.push(stack.pop()); // add right boundary bottom-up
  }
}

function boundaryTraversal(root) {
  if (root === null) return [];
  const boundary = [];
  boundary.push(root.data); // add root
  addLeftBoundary(root, boundary); // add left boundary
  addLeaves(root, boundary); // add leaves
  addRightBoundary(root, boundary); // add right boundary
  return boundary;
}

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

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

boundary.push(root.data);

Add root to boundary

while (curr) { if (!isLeaf(curr)) boundary.push(curr.data); if (curr.left) curr = curr.left; else curr = curr.right; }

Traverse left boundary top-down, skipping leaves

if (isLeaf(root)) { boundary.push(root.data); return; } addLeaves(root.left, boundary); addLeaves(root.right, boundary);

Add all leaf nodes from left to right

while (curr) { if (!isLeaf(curr)) stack.push(curr.data); if (curr.right) curr = curr.right; else curr = curr.left; } while (stack.length > 0) { boundary.push(stack.pop()); }

Traverse right boundary bottom-up, skipping 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 traversal

Space: O(n) for storing the boundary nodes and recursion stack in worst case

vs Alternative: Compared to naive traversal checking all nodes multiple times, this approach efficiently collects boundary nodes in a single pass

Edge Cases

Empty tree

Returns empty boundary list

DSA Javascript

if (root === null) return [];

Tree with only root node

Returns root node as boundary

DSA Javascript

boundary.push(root.data);

Tree with only left subtree

Left boundary and leaves are added correctly, right boundary empty

DSA Javascript

addRightBoundary(root, boundary);

Tree with only right subtree

Right boundary and leaves are added correctly, left boundary empty

DSA Javascript

addLeftBoundary(root, boundary);

When to Use This Pattern

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

Common Mistakes

Mistake: Including leaf nodes twice by adding them in both boundary and leaves steps
Fix: Skip leaf nodes when adding left and right boundaries to avoid duplicates

Mistake: Adding right boundary top-down instead of bottom-up
Fix: Use a stack to collect right boundary nodes and add them in reverse order

Summary

Prints the outer boundary nodes of a binary tree in order: left edge, leaves, right edge.

Use when you need to visit all boundary nodes of a tree without duplicates.

Remember to exclude leaves from left and right boundaries and add right boundary bottom-up.