Boundary Traversal of Binary Tree in DSA Python - Build from Scratch

Boundary Traversal of Binary Tree

📖 Scenario: You are working with a binary tree data structure that represents a hierarchy of tasks in a project. You want to collect the tasks that lie on the boundary of this tree to review the outermost tasks first.

🎯 Goal: Build a program that performs a boundary traversal of a binary tree. The boundary traversal includes the left boundary (excluding leaves), all the leaf nodes, and the right boundary (excluding leaves) in reverse order.

📋 What You'll Learn

Create a binary tree with the exact structure given

Define helper functions to collect left boundary, leaves, and right boundary

Combine these parts to get the full boundary traversal list

Print the boundary traversal as a list of node values

💡 Why This Matters

🌍 Real World

Boundary traversal helps in scenarios like reviewing outermost tasks in a project hierarchy or analyzing edge nodes in network topologies.

💼 Career

Understanding tree traversals is essential for software engineers working with hierarchical data, databases, and UI component trees.

1

Create the Binary Tree Structure

Create a class called Node with an __init__ method that takes data, left, and right parameters. Then create the exact binary tree below by creating Node instances and linking them: - Root node with data 20 - Root's left child with data 8 - Root's right child with data 22 - Node 8's left child with data 4 - Node 8's right child with data 12 - Node 12's left child with data 10 - Node 12's right child with data 14 - Node 22's right child with data 25

DSA Python

# Define Node class and create the binary tree as described
# Your code here

Hint

Define the Node class first. Then create the root node and assign its left and right children as described. Continue linking children to build the full tree.

2

Define Helper Functions for Boundary Traversal

Define three functions: print_left_boundary(node, boundary), print_leaves(node, boundary), and print_right_boundary(node, boundary). Each function takes a node and a list boundary to append node data. - print_left_boundary should add nodes on the left boundary excluding leaves. - print_leaves should add all leaf nodes. - print_right_boundary should add nodes on the right boundary excluding leaves, but in reverse order. Write the function headers and empty bodies (use pass for now).

DSA Python

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

root = Node(20)
root.left = Node(8)
root.right = Node(22)
root.left.left = Node(4)
root.left.right = Node(12)
root.left.right.left = Node(10)
root.left.right.right = Node(14)
root.right.right = Node(25)

# Define print_left_boundary(node, boundary)
# Define print_leaves(node, boundary)
# Define print_right_boundary(node, boundary)
# Your code here

Hint

Write the function headers exactly as def print_left_boundary(node, boundary): and use pass inside for now.

3

Implement Boundary Traversal Logic

Implement the three functions: - In print_left_boundary, add node data to boundary while traversing left boundary excluding leaves. - In print_leaves, add node data to boundary if the node is a leaf. - In print_right_boundary, add node data to a temporary list while traversing right boundary excluding leaves, then add them in reverse to boundary. Then create a list boundary, add the root data, call these functions in order to collect the full boundary traversal.

DSA Python

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

root = Node(20)
root.left = Node(8)
root.right = Node(22)
root.left.left = Node(4)
root.left.right = Node(12)
root.left.right.left = Node(10)
root.left.right.right = Node(14)
root.right.right = Node(25)

def print_left_boundary(node, boundary):
    # Your code here

def print_leaves(node, boundary):
    # Your code here

def print_right_boundary(node, boundary):
    # Your code here

boundary = [root.data]
# Call the functions to fill boundary list
# Your code here

Hint

Use recursion to traverse left boundary, leaves, and right boundary. Append node data to boundary list accordingly. Remember to add right boundary nodes in reverse order.

4

Print the Boundary Traversal Result

Print the boundary list to display the boundary traversal of the binary tree.

DSA Python

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

root = Node(20)
root.left = Node(8)
root.right = Node(22)
root.left.left = Node(4)
root.left.right = Node(12)
root.left.right.left = Node(10)
root.left.right.right = Node(14)
root.right.right = Node(25)

def print_left_boundary(node, boundary):
    if node:
        if node.left:
            boundary.append(node.data)
            print_left_boundary(node.left, boundary)
        elif node.right:
            boundary.append(node.data)
            print_left_boundary(node.right, boundary)


def print_leaves(node, boundary):
    if node:
        print_leaves(node.left, boundary)
        if node.left is None and node.right is None:
            boundary.append(node.data)
        print_leaves(node.right, boundary)


def print_right_boundary(node, boundary):
    if node:
        if node.right:
            print_right_boundary(node.right, boundary)
            boundary.append(node.data)
        elif node.left:
            print_right_boundary(node.left, boundary)
            boundary.append(node.data)


boundary = [root.data]
print_left_boundary(root.left, boundary)
print_leaves(root.left, boundary)
print_leaves(root.right, boundary)
print_right_boundary(root.right, boundary)

# Print the boundary list
# Your code here

Hint

Use print(boundary) to display the final boundary traversal list.

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