Boundary Traversal of Binary Tree in DSA Rust - Execution Trace

Concept Flow - Boundary Traversal of Binary Tree

Start at root

↓

Add root to boundary

↓

Traverse left boundary down

↓

Traverse leaves left to right

↓

Traverse right boundary up

↓

Combine all parts

↓

Boundary traversal complete

The traversal collects nodes from the root, then left boundary top-down, leaves left to right, and right boundary bottom-up to form the boundary.

Execution Sample

DSA Rust

fn boundary_traversal(root: &Option<Box<TreeNode>>) -> Vec<i32> {
    // Collect root, left boundary, leaves, right boundary
}

This code collects the boundary nodes of a binary tree in anti-clockwise order.

Execution Table

Step	Operation	Nodes Visited	Pointer Changes	Visual State
1	Start at root	1 (root)	root pointer at node 1	Boundary: [1]
2	Traverse left boundary down	2, 4	left pointer moves down left subtree	Boundary: [1, 2, 4]
3	Traverse leaves left to right	7, 8, 9, 10	leaf pointers visit all leaves	Boundary: [1, 2, 4, 7, 8, 9, 10]
4	Traverse right boundary up	3, 6	right pointer moves up right subtree	Boundary: [1, 2, 4, 7, 8, 9, 10, 6, 3]
5	Combine all parts	All boundary nodes	No pointer changes	Final Boundary: [1, 2, 4, 7, 8, 9, 10, 6, 3]
6	Traversal complete	N/A	N/A	Traversal ends

💡 All boundary nodes collected, traversal ends

Variable Tracker

Variable	Start	After Step 1	After Step 2	After Step 3	After Step 4	Final
boundary	[]	[1]	[1, 2, 4]	[1, 2, 4, 7, 8, 9, 10]	[1, 2, 4, 7, 8, 9, 10, 6, 3]	[1, 2, 4, 7, 8, 9, 10, 6, 3]
current_left	root	node 1	node 2	node 4	node 4	node 4
current_right	root	node 1	node 1	node 3	node 6	node 6

Key Moments - 3 Insights

Why do we not include leaf nodes again when traversing left and right boundaries?

Leaf nodes are collected separately in the leaves traversal step (Step 3). Including them again in left or right boundary would cause duplicates, as shown in execution_table rows 2 and 3.

Why is the right boundary traversed bottom-up instead of top-down?

Right boundary nodes are added in reverse order to maintain anti-clockwise traversal. This is why in Step 4, nodes 6 and 3 are added after leaves, ensuring correct order.

What happens if the tree has only root node?

Only the root node is added to boundary (Step 1). Left and right boundaries and leaves traversal do nothing, so boundary is just [root], as no further nodes exist.

Visual Quiz - 3 Questions

Look at the execution_table, what is the boundary list after Step 3?

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

B [1, 2, 4, 7, 8, 9, 10]

C [1, 2, 4]

D [1]

💡 Hint

Check the 'Visual State' column at Step 3 in execution_table.

At which step does the traversal add the right boundary nodes?

A Step 4

B Step 2

C Step 3

D Step 5

💡 Hint

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

If the tree has no left subtree, how would the boundary list change after Step 2?

A It includes right boundary nodes

B It becomes empty

C It remains [1]

D It includes leaves only

💡 Hint

Refer to variable_tracker for 'boundary' after Step 2 and consider no left subtree.

Concept Snapshot

Boundary Traversal of Binary Tree:
- Start at root, add root to boundary
- Traverse left boundary top-down (excluding leaves)
- Traverse all leaf nodes left to right
- Traverse right boundary bottom-up (excluding leaves)
- Combine all parts for full boundary in anti-clockwise order

Full Transcript

Boundary traversal of a binary tree collects nodes on the outer edge in anti-clockwise order. It starts by adding the root node, then traverses the left boundary from top to bottom excluding leaves, collects all leaf nodes from left to right, and finally traverses the right boundary from bottom to top excluding leaves. This ensures no duplicates and correct order. The execution table shows each step with nodes visited and the boundary list growing. Key moments clarify why leaves are separate and why right boundary is reversed. The visual quiz tests understanding of these steps and boundary list states.

Practice

1. What is the main purpose of the Boundary Traversal of Binary Tree?

easy

A. To print nodes in post-order traversal

B. To print nodes level by level

C. To print nodes in in-order traversal

D. To print all nodes on the boundary in anti-clockwise direction

Solution

1. Step 1: Understand boundary traversal definition

   Boundary traversal prints nodes on the edges of the tree: left boundary, leaves, and right boundary.

2. Step 2: Identify traversal direction

   The traversal is done in anti-clockwise order starting from root, left boundary, leaves, then right boundary.

3. Final Answer:

   To print all nodes on the boundary in anti-clockwise direction -> Option D

4. Quick Check:

   Boundary traversal = anti-clockwise boundary nodes [OK]

Hint: Boundary traversal prints edges anti-clockwise [OK]

Common Mistakes:

• Confusing boundary traversal with level order traversal
• Including internal nodes not on boundary
• Printing right boundary in clockwise order

2. Which of the following Rust function signatures is correct for a function that performs boundary traversal on a binary tree node defined as struct Node { val: i32, left: Option, right: Option }?

easy

A. fn boundary_traversal(root: Node) -> Vec<i32>

B. fn boundary_traversal(root: &Option) -> Vec<i32>

C. fn boundary_traversal(root: &Node) -> Vec<i32>

D. fn boundary_traversal(root: Option<Node>) -> Vec<i32>

Solution

1. Step 1: Analyze ownership and borrowing in Rust

   Binary tree nodes are wrapped in Option to allow null and heap allocation. Passing by reference avoids ownership transfer.

2. Step 2: Match function signature with correct parameter type

   Using &Option allows borrowing the root node safely without moving ownership.

3. Final Answer:

   fn boundary_traversal(root: &Option) -> Vec<i32> -> Option B

4. Quick Check:

   Borrow Option for traversal [OK]

Hint: Use &Option to borrow tree root safely [OK]

Common Mistakes:

• Passing Node by value causes ownership move
• Using Option<Node> instead of Option
• Using &Node without Option wrapper

3. Given the following Rust code snippet for boundary traversal, what will be the output printed for the tree below? Tree structure: ``` 1 / \ 2 3 / \ \ 4 5 6 / \ / 7 8 9 ``` Code snippet:

fn main() {
    let root = Some(Box::new(Node {
        val: 1,
        left: Some(Box::new(Node {
            val: 2,
            left: Some(Box::new(Node { val: 4, left: None, right: None })),
            right: Some(Box::new(Node {
                val: 5,
                left: Some(Box::new(Node { val: 7, left: None, right: None })),
                right: Some(Box::new(Node { val: 8, left: None, right: None })),
            })),
        })),
        right: Some(Box::new(Node {
            val: 3,
            left: None,
            right: Some(Box::new(Node {
                val: 6,
                left: Some(Box::new(Node { val: 9, left: None, right: None })),
                right: None,
            })),
        })),
    }));
    let result = boundary_traversal(&root);
    println!("{:?}", result);
}

medium

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

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

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

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

Solution

1. Step 1: Identify boundary nodes in anti-clockwise order

   Root: 1; Left boundary (excluding leaves): 2; Leaves (left-to-right): 4, 7, 8, 9; Right boundary (excluding leaves, bottom-up): 6, 3.

2. Step 2: Combine nodes without duplicates

   Boundary traversal = [1, 2, 4, 7, 8, 9, 6, 3]

3. Final Answer:

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

4. Quick Check:

   Boundary nodes = [1,2,4,7,8,9,6,3] [OK]

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

Common Mistakes:

• Including internal nodes like 5 in boundary
• Adding right boundary top-down instead of bottom-up
• Missing leaf nodes on right subtree

4. The following Rust function attempts to perform boundary traversal but has a bug. What is the main issue?

fn print_left_boundary(node: &Option) {
    if let Some(n) = node {
        if n.left.is_some() {
            println!("{}", n.val);
            print_left_boundary(&n.left);
        } else if n.right.is_some() {
            println!("{}", n.val);
            print_left_boundary(&n.right);
        }
    }
}

medium

A. It incorrectly recurses on the right child when the left child is absent

B. It does not print the root node

C. It causes infinite recursion on leaf nodes

D. It skips nodes that have both left and right children

Solution

1. Step 1: Analyze recursion logic

   The function recurses on the left child if present, but falls back to recursing on the right child if no left child. For left boundary, always prefer and recurse only on left child (stop if absent).

2. Step 2: Understand boundary traversal rule for left boundary

   This incorrect fallback includes right subtree nodes in the left boundary traversal.

3. Final Answer:

   It incorrectly recurses on the right child when the left child is absent -> Option A

4. Quick Check:

   Left boundary: recurse left only [OK]

Hint: Always recurse on left child only for left boundary [OK]

Common Mistakes:

• Recursing on right child when left is absent in left boundary
• Not handling None nodes properly
• Incorrectly printing leaves in left boundary

5. You want to modify the boundary traversal to print nodes in clockwise order starting from root. Which of the following changes is correct to achieve this?

hard

A. Print leaves first, then left boundary, then right boundary, then root last

B. Print root, then left boundary top-down, leaves left to right, then right boundary bottom-up

C. Print root, then right boundary top-down, leaves right to left, then left boundary bottom-up

D. Print right boundary bottom-up, leaves left to right, then left boundary top-down, root last

Solution

1. Step 1: Understand clockwise boundary traversal order

   Clockwise traversal starts at root, then right boundary top-down, leaves from right to left, then left boundary bottom-up.

2. Step 2: Match the option with correct order

   Print root, then right boundary top-down, leaves right to left, then left boundary bottom-up matches this order exactly, ensuring correct clockwise traversal.

3. Final Answer:

   Print root, then right boundary top-down, leaves right to left, then left boundary bottom-up -> Option C

4. Quick Check:

   Clockwise boundary = root + right + leaves + left reversed [OK]

Hint: Clockwise = root, right boundary down, leaves right-left, left boundary up [OK]

Common Mistakes:

• Using anti-clockwise order for clockwise traversal
• Printing leaves left to right instead of right to left
• Reversing boundaries incorrectly