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

Boundary Traversal of Binary Tree

📖 Scenario: Imagine you have a family tree represented as a binary tree. You want to collect the names of family members who are on the outer edge of the tree, starting from the oldest ancestor on the left, going around the bottom, and ending at the oldest ancestor on the right.

🎯 Goal: Build a Rust program that performs a boundary traversal of a binary tree. The program will collect and print the nodes on the left boundary, all leaf nodes, and the right boundary in order.

📋 What You'll Learn

Create a binary tree structure with nodes containing integer values.

Implement functions to collect the left boundary, leaf nodes, and right boundary separately.

Combine these parts to perform the full boundary traversal.

Print the boundary traversal as a sequence of node values.

💡 Why This Matters

🌍 Real World

Boundary traversal is useful in graphical applications, tree visualization, and extracting edge elements in hierarchical data.

💼 Career

Understanding tree traversals and recursive algorithms is essential for software engineering roles involving data structures, algorithms, and system design.

1

Create the Binary Tree Structure and Sample Tree

Create a struct called Node with fields data: i32, left: Option, and right: Option. Then create a sample binary tree called root with this exact structure:

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

DSA Rust

# Define the Node struct and create the sample tree
# Your code here

Hint

Use Option<Box<Node>> for left and right children to allow empty branches.

Build the tree from bottom up inside Some(Box::new(Node { ... })) wrappers.

2

Add Helper Functions to Collect Left Boundary and Leaf Nodes

Add two functions: fn left_boundary(node: &Option<Box<Node>>, res: &mut Vec<i32>) and fn leaf_nodes(node: &Option<Box<Node>>, res: &mut Vec<i32>). The left_boundary function should add all left boundary nodes except leaves to res. The leaf_nodes function should add all leaf nodes to res. Call these functions from main with root and an empty vector boundary.

DSA Rust

struct Node {
    data: i32,
    left: Option>,
    right: Option>,
}

fn main() {
    let root = Some(Box::new(Node {
        data: 1,
        left: Some(Box::new(Node {
            data: 2,
            left: Some(Box::new(Node {
                data: 4,
                left: None,
                right: None,
            })),
            right: Some(Box::new(Node {
                data: 5,
                left: Some(Box::new(Node {
                    data: 7,
                    left: None,
                    right: None,
                })),
                right: Some(Box::new(Node {
                    data: 8,
                    left: None,
                    right: None,
                })),
            })),
        })),
        right: Some(Box::new(Node {
            data: 3,
            left: None,
            right: Some(Box::new(Node {
                data: 6,
                left: None,
                right: None,
            })),
        })),
    }));

    let mut boundary = Vec::new();
    // Add calls to left_boundary and leaf_nodes functions here
    // Your code here
}

// Define left_boundary function
// Define leaf_nodes function

Hint

For left_boundary, add nodes going down the left side, skipping leaves.

For leaf_nodes, add nodes with no children.

Call these functions from main with root and boundary.

3

Add Function to Collect Right Boundary and Complete Boundary Traversal

Add a function fn right_boundary(node: &Option<Box<Node>>, res: &mut Vec<i32>) that adds right boundary nodes except leaves to res in bottom-up order. In main, call this function with root.right and a new vector right_bound. Then append right_bound reversed to boundary.

DSA Rust

struct Node {
    data: i32,
    left: Option>,
    right: Option>,
}

fn left_boundary(node: &Option>, res: &mut Vec) {
    if let Some(n) = node {
        if n.left.is_some() {
            res.push(n.data);
            left_boundary(&n.left, res);
        } else if n.right.is_some() {
            res.push(n.data);
            left_boundary(&n.right, res);
        }
    }
}

fn leaf_nodes(node: &Option>, res: &mut Vec) {
    if let Some(n) = node {
        if n.left.is_none() && n.right.is_none() {
            res.push(n.data);
        } else {
            leaf_nodes(&n.left, res);
            leaf_nodes(&n.right, res);
        }
    }
}

// Define right_boundary function here

fn main() {
    let root = Some(Box::new(Node {
        data: 1,
        left: Some(Box::new(Node {
            data: 2,
            left: Some(Box::new(Node {
                data: 4,
                left: None,
                right: None,
            })),
            right: Some(Box::new(Node {
                data: 5,
                left: Some(Box::new(Node {
                    data: 7,
                    left: None,
                    right: None,
                })),
                right: Some(Box::new(Node {
                    data: 8,
                    left: None,
                    right: None,
                })),
            })),
        })),
        right: Some(Box::new(Node {
            data: 3,
            left: None,
            right: Some(Box::new(Node {
                data: 6,
                left: None,
                right: None,
            })),
        })),
    }));

    let mut boundary = Vec::new();
    if let Some(r) = &root {
        boundary.push(r.data);
        left_boundary(&r.left, &mut boundary);
        leaf_nodes(&r.left, &mut boundary);
        leaf_nodes(&r.right, &mut boundary);
    }
    // Add right_boundary call and append reversed results here
    // Your code here
}

Hint

Traverse the right boundary from top to bottom recursively, but add nodes after recursion to get bottom-up order.

Collect right boundary nodes in a separate vector, then append to main boundary vector.

4

Print the Boundary Traversal Result

Add a println! statement in main to print the boundary vector as space-separated values on one line.

DSA Rust

struct Node {
    data: i32,
    left: Option>,
    right: Option>,
}

fn left_boundary(node: &Option>, res: &mut Vec) {
    if let Some(n) = node {
        if n.left.is_some() {
            res.push(n.data);
            left_boundary(&n.left, res);
        } else if n.right.is_some() {
            res.push(n.data);
            left_boundary(&n.right, res);
        }
    }
}

fn leaf_nodes(node: &Option>, res: &mut Vec) {
    if let Some(n) = node {
        if n.left.is_none() && n.right.is_none() {
            res.push(n.data);
        } else {
            leaf_nodes(&n.left, res);
            leaf_nodes(&n.right, res);
        }
    }
}

fn right_boundary(node: &Option>, res: &mut Vec) {
    if let Some(n) = node {
        if n.right.is_some() {
            right_boundary(&n.right, res);
            res.push(n.data);
        } else if n.left.is_some() {
            right_boundary(&n.left, res);
            res.push(n.data);
        }
    }
}

fn main() {
    let root = Some(Box::new(Node {
        data: 1,
        left: Some(Box::new(Node {
            data: 2,
            left: Some(Box::new(Node {
                data: 4,
                left: None,
                right: None,
            })),
            right: Some(Box::new(Node {
                data: 5,
                left: Some(Box::new(Node {
                    data: 7,
                    left: None,
                    right: None,
                })),
                right: Some(Box::new(Node {
                    data: 8,
                    left: None,
                    right: None,
                })),
            })),
        })),
        right: Some(Box::new(Node {
            data: 3,
            left: None,
            right: Some(Box::new(Node {
                data: 6,
                left: None,
                right: None,
            })),
        })),
    }));

    let mut boundary = Vec::new();
    if let Some(r) = &root {
        boundary.push(r.data);
        left_boundary(&r.left, &mut boundary);
        leaf_nodes(&r.left, &mut boundary);
        leaf_nodes(&r.right, &mut boundary);
        let mut right_bound = Vec::new();
        right_boundary(&r.right, &mut right_bound);
        boundary.extend(right_bound);
    }
    // Print the boundary vector as space-separated values
    // Your code here
}

Hint

Use a for loop to print each value in boundary followed by a space.

End with println!() to move to the next line.

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