Boundary Traversal of Binary Tree in DSA Python - Practice Problems & Challenges

Challenge - 5 Problems

❓ Predict Output

intermediate

Output of Boundary Traversal on a Simple Binary Tree

What is the output of the boundary traversal for the given binary tree?

DSA Python

class Node:
    def __init__(self, val):
        self.val = val
        self.left = None
        self.right = None

def printBoundary(root):
    res = []
    def leftBoundary(node):
        if node and (node.left or node.right):
            res.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:
                res.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)
            res.append(node.val)

    if root:
        res.append(root.val)
        leftBoundary(root.left)
        leaves(root.left)
        leaves(root.right)
        rightBoundary(root.right)
    return res

root = Node(1)
root.left = Node(2)
root.right = Node(3)
root.left.left = Node(4)
root.left.right = Node(5)
root.right.left = Node(6)
root.right.right = Node(7)

output = printBoundary(root)
print(output)

A [1, 2, 4, 5, 6, 7, 3]

B [1, 4, 2, 5, 6, 7, 3]

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

D [1, 2, 4, 5, 6, 3, 7]

💡 Hint

Remember the boundary traversal order: root, left boundary (excluding leaves), leaves, right boundary (excluding leaves, in reverse).

The boundary traversal starts with the root (1), then left boundary nodes (2), then all leaves from left to right (4, 5, 6, 7), and finally the right boundary nodes in reverse order (3).

🧠 Conceptual

intermediate

Understanding Boundary Traversal Components

Which of the following correctly describes the order of nodes visited in a boundary traversal of a binary tree?

A Left boundary nodes, root node, leaf nodes, right boundary nodes

B Root node, all leaf nodes, left boundary nodes, right boundary nodes

C Root node, left boundary nodes (excluding leaves), leaf nodes, right boundary nodes (excluding leaves, in reverse)

D Leaf nodes, left boundary nodes, root node, right boundary nodes

💡 Hint

Think about the traversal starting from the root and how boundaries are defined.

Boundary traversal visits the root first, then the left boundary excluding leaves, then all leaves from left to right, and finally the right boundary excluding leaves in reverse order.

🔧 Debug

advanced

Identify the Bug in Boundary Traversal Code

Given the following code snippet for boundary traversal, what error will it produce when run on a binary tree with only a root node?

DSA Python

def printBoundary(root):
    res = []
    def leftBoundary(node):
        if node and (node.left or node.right):
            res.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:
                res.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)
            res.append(node.val)

    res.append(root.val)
    leftBoundary(root.left)
    leaves(root.left)
    leaves(root.right)
    rightBoundary(root.right)
    return res

root = Node(10)
print(printBoundary(root))

A [10] as output without errors

B AttributeError because root.left is None and passed to leftBoundary

C TypeError because res.append is called on None

D RecursionError due to infinite recursion in leaves function

💡 Hint

Check how the functions handle None nodes and if recursion stops correctly.

The code correctly handles None nodes by checking if node is None before recursing, so it returns [10] without errors for a single root node.

🚀 Application

advanced

Boundary Traversal Output for an Unbalanced Tree

What is the boundary traversal output for the following unbalanced binary tree? Structure: - Root: 10 - Root.left: 20 - Root.left.left: 40 - Root.left.left.right: 50 - Root.right: 30 - Root.right.right: 60 - Root.right.right.left: 70

A [10, 20, 40, 50, 30, 70, 60]

B [10, 20, 40, 50, 70, 30, 60]

C [10, 20, 40, 50, 70, 60]

D [10, 20, 40, 50, 70, 60, 30]

💡 Hint

Remember to include left boundary excluding leaves, all leaves, and right boundary excluding leaves in reverse.

Left boundary excluding leaves: 20, 40 (40 has a right child so it's boundary). Leaves: 50, 70. Right boundary excluding leaves in reverse: 60, 30. Root is 10 at start.

🧠 Conceptual

expert

Complexity Analysis of Boundary Traversal

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

A O(n^2), because leaves and boundaries are processed separately multiple times

B O(n), because each node is visited at most once during the traversal

C O(n log n), due to recursive calls on left and right subtrees

D O(log n), since only boundary nodes are visited

💡 Hint

Consider how many times each node is processed in the traversal.

Each node is visited once either as part of left boundary, leaves, or right boundary, so total time is linear in number of nodes.

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