Boundary Traversal of Binary Tree in DSA Javascript - Execution Trace

Concept Flow - Boundary Traversal of Binary Tree

Start at root

↓

Add root to boundary

↓

Traverse left boundary (top-down)

↓

Traverse leaf nodes (left to right)

↓

Traverse right boundary (bottom-up)

↓

Combine all parts for boundary traversal

The traversal collects nodes from the left boundary top-down, then all leaf nodes left to right, and finally the right boundary bottom-up, starting from the root.

Execution Sample

DSA Javascript

function boundaryTraversal(root) {
  if (!root) return [];
  let result = [root.val];
  // left boundary
  // leaf nodes
  // right boundary
  return result;
}

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

Execution Table

Step	Operation	Nodes in Boundary List	Pointer Changes	Visual State
1	Start at root	[1]	root -> 1	1 / \ 2 3 / \ \ 4 5 6
2	Add left boundary (excluding leaves)	[1, 2]	current -> 2	1 / \ 2 3 / \ \ 4 5 6
3	Add leaf nodes (left to right)	[1, 2, 4, 5, 6]	leaf nodes visited: 4,5,6	1 / \ 2 3 / \ \ 4 5 6
4	Add right boundary (excluding leaves) bottom-up	[1, 2, 4, 5, 6, 3]	current -> 3	1 / \ 2 3 / \ \ 4 5 6
5	Traversal complete	[1, 2, 4, 5, 6, 3]	None	Final boundary: 1 -> 2 -> 4 -> 5 -> 6 -> 3

💡 All boundary nodes collected: left boundary, leaves, right boundary

Variable Tracker

Variable	Start	After Step 2	After Step 3	After Step 4	Final
result	[]	[1, 2]	[1, 2, 4, 5, 6]	[1, 2, 4, 5, 6, 3]	[1, 2, 4, 5, 6, 3]
current (left boundary)	1	2	2	2	2
current (right boundary)	null	null	null	3	3

Key Moments - 3 Insights

Why do we exclude leaf nodes when adding left and right boundaries?

Because leaf nodes are added separately in the leaf traversal step to avoid duplicates, as shown in execution_table rows 2 and 3.

Why is the right boundary added in bottom-up order?

To maintain the correct boundary order, the right boundary nodes are collected top-down but added to the result in reverse (bottom-up), as seen in execution_table row 4.

What happens if the tree has only root node?

The traversal adds only the root node to the boundary list and stops, as shown in execution_table row 1.

Visual Quiz - 3 Questions

Look at the execution_table, what nodes are in the boundary list after step 3?

A [1, 2]

B [1, 2, 3]

C [1, 2, 4, 5, 6]

D [1, 3, 6]

💡 Hint

Check the 'Nodes in Boundary List' column at step 3 in execution_table.

At which step is the right boundary added to the boundary list?

A Step 4

B Step 3

C Step 2

D Step 5

💡 Hint

Look at the 'Operation' column in execution_table for when right boundary is added.

If the tree had no right subtree, how would the boundary list change after step 4?

A Right boundary nodes would be added as usual

B Right boundary nodes would be empty, so no change after step 4

C Left boundary nodes would be added again

D Leaf nodes would be skipped

💡 Hint

Refer to variable_tracker and execution_table steps for right boundary additions.

Concept Snapshot

Boundary Traversal of Binary Tree:
- Start at root, add root to result
- Traverse left boundary top-down (exclude leaves)
- Traverse all leaf nodes left to right
- Traverse right boundary bottom-up (exclude leaves)
- Combine all for final boundary list

Full Transcript

Boundary traversal collects nodes on the outer edge of a binary tree. It starts by adding the root node. Then it adds the left boundary nodes from top to bottom, excluding leaf nodes to avoid duplicates. Next, it adds all leaf nodes from left to right. Finally, it adds the right boundary nodes from bottom to top, again excluding leaves. This order ensures the boundary is traversed correctly without repeating nodes. The execution table shows each step with the nodes added and the tree state. The variable tracker follows the result list and pointers used. Key moments clarify why leaves are excluded in boundary traversals and why the right boundary is added in reverse order. The visual quiz tests understanding of these steps and their effects on the boundary list.

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