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.

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 an 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: Compare options with definition

   Only To print all nodes on the boundary in an anti-clockwise direction describes printing all boundary nodes in anti-clockwise order.

3. Final Answer:

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

4. Quick Check:

   Boundary traversal = print boundary nodes anti-clockwise [OK]

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

Common Mistakes:

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

2. Which of the following is the correct way to start the boundary traversal function in JavaScript?

easy

A. function boundaryTraversal(root) { console.log(root.right); }

B. function boundaryTraversal() { return root; }

C. function boundaryTraversal(root) { if (!root) return []; }

D. function boundaryTraversal(root) { return root.left; }

Solution

1. Step 1: Check function signature and base case

   The function should accept root and handle empty tree by returning empty array.

2. Step 2: Validate options

   function boundaryTraversal(root) { if (!root) return []; } correctly defines function with root parameter and returns empty array if root is null.

3. Final Answer:

   function boundaryTraversal(root) { if (!root) return []; } -> Option C

4. Quick Check:

   Function starts with root check and empty return [OK]

Hint: Always check for empty tree at start of traversal function [OK]

Common Mistakes:

• Omitting root parameter
• Not handling empty tree
• Returning wrong values at start

3. Given the binary tree:

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

What is the output of boundary traversal (anti-clockwise)?

medium

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

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

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

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

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-up excluding leaves

   Right boundary: 3

4. Step 4: Combine in anti-clockwise order

   Boundary traversal: 1 (root), 2 (left boundary), 4 (leaf), 7, 8, 9, 6 (leaf), 3 (right boundary)

5. Final Answer:

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

6. Quick Check:

   Boundary nodes combined anti-clockwise = [1, 2, 4, 7, 8, 9, 6, 3] [OK]

Hint: List left boundary, leaves, then right boundary reversed [OK]

Common Mistakes:

• Including internal nodes as leaves
• Adding right boundary leaves twice
• Wrong order of nodes

4. Consider this code snippet for boundary traversal in JavaScript:

function printLeaves(node, result) {
  if (!node) return;
  if (!node.left && !node.right) {
    result.push(node.data);
  }
  printLeaves(node.left, result);
  printLeaves(node.right, result);
}

What is the bug in this code?

medium

A. It visits leaves in left to right order correctly

B. It pushes non-leaf nodes into result

C. It visits leaves in wrong order (right before left)

D. It does not check for null node before recursion

Solution

1. Step 1: Analyze leaf detection and recursion order

   Code checks if node is leaf and pushes data, then recursively visits left then right child.

2. Step 2: Verify leaf order correctness

   Visiting left subtree before right ensures leaves are collected left to right.

3. Step 3: Check for bugs

   No bug found; code correctly collects leaves in left to right order.

4. Final Answer:

   It visits leaves in left to right order correctly -> Option A

5. Quick Check:

   Leaf nodes collected left to right = It visits leaves in left to right order correctly [OK]

Hint: Left subtree first ensures left-to-right leaf order [OK]

Common Mistakes:

• Thinking recursion order is reversed
• Assuming non-leaf nodes are pushed
• Missing base case check

5. You want to perform boundary traversal on a binary tree but exclude all leaf nodes that have even values. Which approach correctly adapts the traversal?

hard

A. Modify leaf collection to skip leaves with even values during traversal

B. Skip left and right boundary nodes if they are even

C. Only collect leaves and ignore boundaries

D. Collect all nodes and filter even leaves after traversal

Solution

1. Step 1: Understand boundary traversal parts

   Boundary traversal includes left boundary, leaves, and right boundary.

2. Step 2: Identify where to exclude even leaves

   Only leaf nodes need filtering; boundaries remain unchanged.

3. Step 3: Adapt leaf collection function

   Modify leaf collection to check leaf value and skip if even.

4. Final Answer:

   Modify leaf collection to skip leaves with even values during traversal -> Option A

5. Quick Check:

   Filter leaves during traversal, not boundaries [OK]

Hint: Filter leaves during leaf collection step only [OK]

Common Mistakes:

• Filtering boundary nodes incorrectly
• Filtering after traversal causing extra work
• Ignoring leaf filtering altogether