Boundary Traversal of Binary Tree in DSA Javascript - Cheat Sheet & Quick Revision

Recall & Review

beginner

What is the Boundary Traversal of a binary tree?

Boundary Traversal means visiting the nodes on the outer edge of the tree in a specific order: left boundary (top to bottom), leaves (left to right), and right boundary (bottom to top).

beginner

Which parts of the binary tree are included in the boundary traversal?

The boundary traversal includes three parts: 1) Left boundary nodes (excluding leaves), 2) All leaf nodes, 3) Right boundary nodes (excluding leaves).

intermediate

Why do we exclude leaf nodes when collecting left and right boundaries in boundary traversal?

Leaf nodes are excluded from left and right boundaries to avoid duplication because all leaf nodes are collected separately in the leaf nodes step.

intermediate

In boundary traversal, how is the right boundary collected differently from the left boundary?

The right boundary is collected from bottom to top, so nodes are stored in reverse order before adding to the result, unlike the left boundary which is collected top to bottom.

beginner

Show a simple JavaScript function signature for boundary traversal of a binary tree.

function boundaryTraversal(root) {
  // root is the root node of the binary tree
  // returns an array of node values in boundary order
}

Which nodes are visited first in boundary traversal of a binary tree?

A Left boundary nodes from top to bottom

B Leaf nodes from left to right

C Right boundary nodes from bottom to top

D Root node only

Boundary traversal starts with the left boundary nodes from top to bottom.

Why do we collect leaf nodes separately in boundary traversal?

A Because leaf nodes are not part of the tree

B To avoid duplication of leaf nodes in left and right boundaries

C To avoid missing any leaf nodes

D Leaf nodes are collected last for sorting

Leaf nodes are collected separately to avoid duplication since they can appear in both left and right boundaries.

How is the right boundary added to the result in boundary traversal?

A From bottom to top

B From top to bottom

C In random order

D Right boundary is not included

Right boundary nodes are added from bottom to top to maintain the correct boundary order.

Which of these nodes is NOT included in the left boundary during boundary traversal?

A Root node

B Left child nodes excluding leaves

C Leaf nodes

D Nodes on the left edge

Leaf nodes are excluded from the left boundary and collected separately.

What is the time complexity of boundary traversal in a binary tree with n nodes?

A O(log n)

B O(1)

C O(n^2)

D O(n)

Boundary traversal visits each node at most once, so the time complexity is O(n).

Explain the steps involved in performing a boundary traversal of a binary tree.

Think about the three parts of the boundary and how to avoid duplicates.

Describe how you would implement boundary traversal in code using simple helper functions.

Divide the problem into smaller parts for clarity.

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