Boundary Traversal of Binary Tree in DSA Rust - 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 following binary tree?

Tree structure:
1
/ \
2 3
/ \ \
4 5 6
/ \
7 8

DSA Rust

struct Node {
    val: i32,
    left: Option<Box<Node>>,
    right: Option<Box<Node>>,
}

fn boundary_traversal(root: &Option<Box<Node>>) -> Vec<i32> {
    fn is_leaf(node: &Option<Box<Node>>) -> bool {
        if let Some(n) = node {
            n.left.is_none() && n.right.is_none()
        } else {
            false
        }
    }

    fn add_left_boundary(node: &Option<Box<Node>>, res: &mut Vec<i32>) {
        let mut curr = node;
        while let Some(n) = curr {
            if !is_leaf(curr) {
                res.push(n.val);
            }
            if n.left.is_some() {
                curr = &n.left;
            } else {
                curr = &n.right;
            }
        }
    }

    fn add_leaves(node: &Option<Box<Node>>, res: &mut Vec<i32>) {
        if let Some(n) = node {
            if is_leaf(node) {
                res.push(n.val);
            } else {
                add_leaves(&n.left, res);
                add_leaves(&n.right, res);
            }
        }
    }

    fn add_right_boundary(node: &Option<Box<Node>>, res: &mut Vec<i32>) {
        let mut curr = node;
        let mut tmp = Vec::new();
        while let Some(n) = curr {
            if !is_leaf(curr) {
                tmp.push(n.val);
            }
            if n.right.is_some() {
                curr = &n.right;
            } else {
                curr = &n.left;
            }
        }
        for val in tmp.into_iter().rev() {
            res.push(val);
        }
    }

    let mut res = Vec::new();
    if root.is_none() {
        return res;
    }
    let root_node = root.as_ref().unwrap();
    if !is_leaf(root) {
        res.push(root_node.val);
    }
    add_left_boundary(&root_node.left, &mut res);
    add_leaves(root, &mut res);
    add_right_boundary(&root_node.right, &mut res);
    res
}

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: None, right: None })),
        })),
    }));

    let result = boundary_traversal(&root);
    println!("{:?}", result);
}

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

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

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

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

💡 Hint

Remember boundary traversal includes left boundary (excluding leaves), all leaves, then right boundary (excluding leaves) in reverse.

The boundary traversal starts with root (1), then left boundary nodes excluding leaves (2), then all leaves from left to right (4,7,8,6), then right boundary nodes excluding leaves in reverse (3). So the output is [1, 2, 4, 7, 8, 6, 3].

❓ Predict Output

intermediate

Boundary Traversal Output for Single Node Tree

What is the output of the boundary traversal for a binary tree with only one node (value 10)?

DSA Rust

struct Node {
    val: i32,
    left: Option<Box<Node>>,
    right: Option<Box<Node>>,
}

fn boundary_traversal(root: &Option<Box<Node>>) -> Vec<i32> {
    fn is_leaf(node: &Option<Box<Node>>) -> bool {
        if let Some(n) = node {
            n.left.is_none() && n.right.is_none()
        } else {
            false
        }
    }

    fn add_left_boundary(node: &Option<Box<Node>>, res: &mut Vec<i32>) {
        let mut curr = node;
        while let Some(n) = curr {
            if !is_leaf(curr) {
                res.push(n.val);
            }
            if n.left.is_some() {
                curr = &n.left;
            } else {
                curr = &n.right;
            }
        }
    }

    fn add_leaves(node: &Option<Box<Node>>, res: &mut Vec<i32>) {
        if let Some(n) = node {
            if is_leaf(node) {
                res.push(n.val);
            } else {
                add_leaves(&n.left, res);
                add_leaves(&n.right, res);
            }
        }
    }

    fn add_right_boundary(node: &Option<Box<Node>>, res: &mut Vec<i32>) {
        let mut curr = node;
        let mut tmp = Vec::new();
        while let Some(n) = curr {
            if !is_leaf(curr) {
                tmp.push(n.val);
            }
            if n.right.is_some() {
                curr = &n.right;
            } else {
                curr = &n.left;
            }
        }
        for val in tmp.into_iter().rev() {
            res.push(val);
        }
    }

    let mut res = Vec::new();
    if root.is_none() {
        return res;
    }
    let root_node = root.as_ref().unwrap();
    if !is_leaf(root) {
        res.push(root_node.val);
    }
    add_left_boundary(&root_node.left, &mut res);
    add_leaves(root, &mut res);
    add_right_boundary(&root_node.right, &mut res);
    res
}

fn main() {
    let root = Some(Box::new(Node { val: 10, left: None, right: None }));
    let result = boundary_traversal(&root);
    println!("{:?}", result);
}

A [10]

B []

C [10, 10]

D [0]

💡 Hint

A single node is also a leaf and the root, so it should appear once.

Since the tree has only one node which is a leaf and root, the boundary traversal returns [10].

🔧 Debug

advanced

Identify the Bug in Right Boundary Traversal

The following Rust function is intended to add the right boundary nodes (excluding leaves) of a binary tree to the result vector in reverse order. What is the bug causing incorrect output?

DSA Rust

fn add_right_boundary(node: &Option<Box<Node>>, res: &mut Vec<i32>) {
    let mut curr = node;
    let mut tmp = Vec::new();
    while let Some(n) = curr {
        if !is_leaf(curr) {
            tmp.push(n.val);
        }
        if n.left.is_some() {
            curr = &n.left;
        } else {
            curr = &n.right;
        }
    }
    for val in tmp.into_iter().rev() {
        res.push(val);
    }
}

A The traversal goes to left child first instead of right child, so right boundary is incorrect.

B The function pushes leaf nodes which should be excluded.

C The vector tmp is not reversed before adding to res.

D The function does not check for None nodes before accessing val.

💡 Hint

Right boundary traversal should prioritize right child over left child.

The bug is that the code moves to left child first, which is wrong for right boundary traversal. It should move to right child first to correctly collect right boundary nodes.

🧠 Conceptual

advanced

Understanding Leaf Node Inclusion in Boundary Traversal

In boundary traversal of a binary tree, why do we add leaf nodes separately after adding left boundary nodes and before adding right boundary nodes?

A Because leaf nodes are always part of the left boundary only.

B Because leaf nodes are not included in left or right boundary traversals and must be added separately to avoid duplicates.

C Because leaf nodes are always part of the right boundary only.

D Because leaf nodes are excluded from the traversal entirely.

💡 Hint

Think about how left and right boundaries exclude leaves to avoid duplication.

Left and right boundary traversals exclude leaf nodes to prevent duplicates. Leaf nodes are added separately to include all leaves exactly once.

🚀 Application

expert

Number of Nodes in Boundary Traversal Result

Given a perfect binary tree of height 3 (levels 0 to 3), how many nodes will be in the boundary traversal result?

A 9

B 15

C 13

D 7

💡 Hint

Count left boundary excluding leaves, all leaves, and right boundary excluding leaves, plus root.

A perfect binary tree of height 3 has 15 nodes. Leaves are at level 3 (8 leaves). Left boundary excluding leaves has 2 nodes, right boundary excluding leaves has 2 nodes, plus root (1). Total = 1 + 2 + 8 + 2 = 13.

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