Boundary Traversal of Binary Tree in DSA Python - Interactive Practice

Practice - 5 Tasks

1fill in blank

easy

Complete the code to check if a node is a leaf node.

DSA Python

def is_leaf(node):
    return node.left is None and node.[1] is None

Drag options to blanks, or click blank then click option'

Aright

Bleft

Cparent

Dchild

Attempts:

3 left

💡 Hint

Common Mistakes

Checking only one child for None

Using incorrect attribute names

The function checks if both left and right children are None, meaning the node is a leaf.

2fill in blank

medium

Complete the code to traverse the left boundary excluding leaf nodes.

DSA Python

def add_left_boundary(root, res):
    curr = root.left
    while curr:
        if not is_leaf(curr):
            res.append(curr.data)
        curr = curr.[1]

Drag options to blanks, or click blank then click option'

Aleft

Bchild

Cparent

Dright

Attempts:

3 left

💡 Hint

Common Mistakes

Using right child instead of left

Appending leaf nodes

We move down the left boundary by following the left child pointers.

3fill in blank

hard

Fix the error in the code to add leaf nodes in left-to-right order.

DSA Python

def add_leaves(root, res):
    if is_leaf(root):
        res.append(root.data)
        return
    if root.left:
        add_leaves(root.[1], res)
    if root.right:
        add_leaves(root.right, res)

Drag options to blanks, or click blank then click option'

Aright

Bparent

Cleft

Dchild

Attempts:

3 left

💡 Hint

Common Mistakes

Recursing on right child first

Using wrong attribute names

To traverse leaves left to right, recurse first on the left child, then on the right child.

4fill in blank

hard

Fill both blanks to traverse the right boundary excluding leaf nodes in bottom-up order.

DSA Python

def add_right_boundary(root, res):
    curr = root.[1]
    temp = []
    while curr:
        if not is_leaf(curr):
            temp.append(curr.data)
        curr = curr.[2]
    for i in reversed(temp):
        res.append(i)

Drag options to blanks, or click blank then click option'

Aright

Bleft

Cparent

Dchild

Attempts:

3 left

💡 Hint

Common Mistakes

Using left child pointer instead of right

Appending nodes in wrong order

Start from the right child of root and move down the right boundary by following the right child pointers, collecting nodes to add in reverse order.

5fill in blank

hard

Fill the blanks to complete the boundary traversal function.

DSA Python

def boundary_traversal(root):
    if root is None:
        return []
    res = [root.data]
    add_left_boundary(root, res)
    add_leaves(root.[1], res)
    add_leaves(root.[2], res)
    add_right_boundary(root, res)
    return res

Drag options to blanks, or click blank then click option'

Aright

Bleft

Cparent

Dchild

Attempts:

3 left

💡 Hint

Common Mistakes

Swapping left and right in leaf collection

Missing leaf nodes

Leaves are collected from left subtree then right subtree. Left boundary and right boundary are added separately.

Practice

1. What does the boundary traversal of a binary tree include?

easy

A. Left boundary, leaves, and right boundary nodes

B. Only leaf nodes

C. Only root node

D. All nodes in level order

Solution

1. Step 1: Understand boundary traversal components

   Boundary traversal includes nodes on the left edge, all leaf nodes, and nodes on the right edge of the tree.

2. Step 2: Compare options with definition

   Only Left boundary, leaves, and right boundary nodes correctly lists left boundary, leaves, and right boundary nodes.

3. Final Answer:

   Left boundary, leaves, and right boundary nodes -> Option A

4. Quick Check:

   Boundary traversal = left boundary + leaves + right boundary [OK]

Hint: Remember boundary = left edge + leaves + right edge [OK]

Common Mistakes:

• Confusing boundary traversal with level order traversal
• Ignoring leaf nodes in boundary traversal
• Including all nodes instead of just edges and leaves

2. Which of the following is the correct Python function signature for boundary traversal of a binary tree?

easy

A. def boundaryTraversal(root, result):

B. def boundaryTraversal(root, left, right):

C. def boundaryTraversal():

D. def boundaryTraversal(root):

Solution

1. Step 1: Identify typical function signature

   Boundary traversal usually takes the root node as input and returns the traversal list.

2. Step 2: Check options for correct signature

   def boundaryTraversal(root): takes only root as input, which is standard and sufficient.

3. Final Answer:

   def boundaryTraversal(root): -> Option D

4. Quick Check:

   Function signature with root only is correct [OK]

Hint: Boundary traversal function needs only root parameter [OK]

Common Mistakes:

• Adding unnecessary parameters like left and right
• Missing root parameter
• Using empty parameter list

3. What is the output of the boundary traversal for the following binary tree?

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

medium

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

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

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

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

Solution

1. Step 1: Identify left boundary nodes

   Left boundary nodes are 1, 2, 4 (excluding leaf duplicates).

2. Step 2: Identify leaf nodes

   Leaves are 4, 7, 8, 9, 6.

3. Step 3: Identify right boundary nodes

   Right boundary nodes are 3, 6 (excluding leaf duplicates), so only 3.

4. Step 4: Combine nodes in order

   Boundary traversal = left boundary (1,2,4) + leaves (7,8,9,6) + right boundary reversed (3) = [1, 2, 4, 7, 8, 9, 6, 3]

5. Final Answer:

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

6. Quick Check:

   Boundary traversal output matches [1, 2, 4, 7, 8, 9, 6, 3] [OK]

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

Common Mistakes:

• Including leaf nodes twice in boundary
• Missing right boundary node 3
• Incorrect order of nodes

4. The following code attempts boundary traversal but misses some nodes. What is the bug?

def boundaryTraversal(root):
    result = []
    def leftBoundary(node):
        if node and (node.left or node.right):
            result.append(node.val)
            if node.left:
                leftBoundary(node.left)
            else:
                leftBoundary(node.right)
    def leaves(node):
        if node:
            leaves(node.left)
            if not node.left and not node.right:
                result.append(node.val)
            leaves(node.right)
    def rightBoundary(node):
        if node and (node.left or node.right):
            if node.right:
                rightBoundary(node.right)
            else:
                rightBoundary(node.left)
            result.append(node.val)
    if root:
        result.append(root.val)
        leftBoundary(root.left)
        leaves(root.left)
        leaves(root.right)
        rightBoundary(root.right)
    return result

medium

A. Leaves function misses leaf nodes on right subtree

B. Right boundary nodes are appended before recursive call

C. Left boundary includes leaf nodes causing duplicates

D. Root node is not added to result

Solution

1. Step 1: Analyze leftBoundary function

   Left boundary adds nodes with children but does not exclude leaf nodes explicitly, so leaf nodes can be added twice.

2. Step 2: Check leaves and rightBoundary functions

   Leaves function correctly adds leaf nodes; rightBoundary appends after recursion, which is correct.

3. Step 3: Identify bug

   Left boundary includes leaf nodes causing duplicates in result.

4. Final Answer:

   Left boundary includes leaf nodes causing duplicates -> Option C

5. Quick Check:

   Left boundary must exclude leaves to avoid duplicates [OK]

Hint: Exclude leaf nodes from left boundary to avoid duplicates [OK]

Common Mistakes:

• Appending right boundary nodes before recursion
• Not adding root node
• Leaves function missing some leaves

5. Given a binary tree where some nodes have only one child, how should the boundary traversal handle nodes with a single child to ensure all boundary nodes are included exactly once?

hard

A. Skip nodes with only one child in boundary traversal

B. Traverse left boundary by always choosing left child if present, else right child; similarly for right boundary, choose right child if present, else left child

C. Include all nodes regardless of position to avoid missing any

D. Only include leaf nodes and root node in boundary traversal

Solution

1. Step 1: Understand boundary traversal with single-child nodes

   When a node has only one child, boundary traversal must follow that child to include all boundary nodes.

2. Step 2: Apply traversal rules

   For left boundary, choose left child if exists; if not, choose right child. For right boundary, choose right child if exists; if not, choose left child.

3. Step 3: Avoid duplicates by excluding leaves in boundary functions

   Leaves are handled separately to avoid duplicates.

4. Final Answer:

   Traverse left boundary by always choosing left child if present, else right child; similarly for right boundary, choose right child if present, else left child -> Option B

5. Quick Check:

   Follow child presence rules to cover all boundary nodes [OK]

Hint: Choose child present on boundary side to cover all nodes [OK]

Common Mistakes:

• Skipping single-child nodes causing missing boundary nodes
• Including all nodes causing duplicates
• Ignoring leaf nodes in traversal