Boundary Traversal of Binary Tree in DSA Rust

Mental Model

We want to visit the outer edge nodes of a tree in a specific order: left edge top-down, leaves left to right, then right edge bottom-up.

Analogy: Imagine walking around the outside of a garden shaped like a tree, first along the left fence, then along the flowers at the bottom, and finally along the right fence going back up.

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

Left boundary: 1 -> 2
Leaves: 4 -> 7 -> 8 -> 9
Right boundary: 6 -> 3

Dry Run Walkthrough

Input: Binary tree: 1 / \ 2 3 / \ \ 4 5 6 / \ / 7 8 9

Goal: Print boundary traversal: left boundary top-down, leaves left to right, right boundary bottom-up without duplicates

Step 1: Add root node 1 to boundary

Boundary: 1

Why: Root is always part of the boundary

Step 2: Traverse left boundary excluding leaves: add 2

Boundary: 1 -> 2

Why: Left edge nodes top-down except leaves to avoid duplicates

Step 3: Add leaf nodes left to right: 4, 7, 8, 9

Boundary: 1 -> 2 -> 4 -> 7 -> 8 -> 9

Why: Leaves are added left to right

Step 4: Traverse right boundary excluding leaves bottom-up: add 6 then 3

Boundary: 1 -> 2 -> 4 -> 7 -> 8 -> 9 -> 6 -> 3

Why: Right edge nodes added bottom-up excluding leaves to avoid duplicates

Result:

1 -> 2 -> 4 -> 7 -> 8 -> 9 -> 6 -> 3

Annotated Code

DSA Rust

use std::rc::Rc;
use std::cell::RefCell;

#[derive(Debug, Clone)]
struct TreeNode {
    val: i32,
    left: Option<Rc<RefCell<TreeNode>>>,
    right: Option<Rc<RefCell<TreeNode>>>,
}

impl TreeNode {
    fn new(val: i32) -> Rc<RefCell<TreeNode>> {
        Rc::new(RefCell::new(TreeNode { val, left: None, right: None }))
    }
}

fn is_leaf(node: &Option<Rc<RefCell<TreeNode>>>) -> bool {
    if let Some(n) = node {
        let n = n.borrow();
        n.left.is_none() && n.right.is_none()
    } else {
        false
    }
}

fn add_left_boundary(node: &Option<Rc<RefCell<TreeNode>>>, boundary: &mut Vec<i32>) {
    let mut curr = node.clone();
    while let Some(n) = curr {
        let n_borrow = n.borrow();
        if !is_leaf(&Some(n.clone())) {
            boundary.push(n_borrow.val);
        }
        if n_borrow.left.is_some() {
            curr = n_borrow.left.clone();
        } else {
            curr = n_borrow.right.clone();
        }
    }
}

fn add_leaves(node: &Option<Rc<RefCell<TreeNode>>>, boundary: &mut Vec<i32>) {
    if let Some(n) = node {
        let n_borrow = n.borrow();
        if is_leaf(node) {
            boundary.push(n_borrow.val);
        } else {
            add_leaves(&n_borrow.left, boundary);
            add_leaves(&n_borrow.right, boundary);
        }
    }
}

fn add_right_boundary(node: &Option<Rc<RefCell<TreeNode>>>, boundary: &mut Vec<i32>) {
    let mut curr = node.clone();
    let mut stack = Vec::new();
    while let Some(n) = curr {
        let n_borrow = n.borrow();
        if !is_leaf(&Some(n.clone())) {
            stack.push(n_borrow.val);
        }
        if n_borrow.right.is_some() {
            curr = n_borrow.right.clone();
        } else {
            curr = n_borrow.left.clone();
        }
    }
    while let Some(val) = stack.pop() {
        boundary.push(val);
    }
}

fn boundary_traversal(root: Option<Rc<RefCell<TreeNode>>>) -> Vec<i32> {
    let mut boundary = Vec::new();
    if root.is_none() {
        return boundary;
    }
    let root_node = root.as_ref().unwrap();
    if !is_leaf(&root) {
        boundary.push(root_node.borrow().val); // add root if not leaf
    }
    add_left_boundary(&root_node.borrow().left, &mut boundary);
    add_leaves(&root, &mut boundary);
    add_right_boundary(&root_node.borrow().right, &mut boundary);
    boundary
}

fn main() {
    // Construct the tree from dry_run input
    let root = TreeNode::new(1);
    let n2 = TreeNode::new(2);
    let n3 = TreeNode::new(3);
    let n4 = TreeNode::new(4);
    let n5 = TreeNode::new(5);
    let n6 = TreeNode::new(6);
    let n7 = TreeNode::new(7);
    let n8 = TreeNode::new(8);
    let n9 = TreeNode::new(9);

    root.borrow_mut().left = Some(n2.clone());
    root.borrow_mut().right = Some(n3.clone());

    n2.borrow_mut().left = Some(n4.clone());
    n2.borrow_mut().right = Some(n5.clone());

    n3.borrow_mut().right = Some(n6.clone());

    n5.borrow_mut().left = Some(n7.clone());
    n5.borrow_mut().right = Some(n8.clone());

    n6.borrow_mut().left = Some(n9.clone());

    let result = boundary_traversal(Some(root));
    for (i, val) in result.iter().enumerate() {
        if i != result.len() - 1 {
            print!("{} -> ", val);
        } else {
            print!("{}", val);
        }
    }
    println!();
}

if !is_leaf(&root) { boundary.push(root_node.borrow().val); // add root if not leaf }

Add root to boundary if it is not a leaf

while let Some(n) = curr { let n_borrow = n.borrow(); if !is_leaf(&Some(n.clone())) { boundary.push(n_borrow.val); } curr = n_borrow.left.clone(); }

Traverse left boundary top-down excluding leaves

if is_leaf(node) { boundary.push(n_borrow.val); } else { add_leaves(&n_borrow.left, boundary); add_leaves(&n_borrow.right, boundary); }

Add leaf nodes in left to right order

while let Some(n) = curr { let n_borrow = n.borrow(); if !is_leaf(&Some(n.clone())) { stack.push(n_borrow.val); } if n_borrow.right.is_some() { curr = n_borrow.right.clone(); } else { curr = n_borrow.left.clone(); } } while let Some(val) = stack.pop() { boundary.push(val); }

Traverse right boundary bottom-up excluding leaves using stack

Output

1 -> 2 -> 4 -> 7 -> 8 -> 9 -> 6 -> 3

Complexity Analysis

Time: O(n) because we visit each node at most once during traversal

Space: O(n) for recursion stack and boundary storage in worst case

vs Alternative: Compared to naive approach that might check all nodes multiple times, this approach visits nodes in a controlled manner to avoid duplicates and extra work

Edge Cases

Empty tree

Returns empty boundary list

DSA Rust

if root.is_none() {
        return boundary;
    }

Tree with only root node

Returns root value as boundary

DSA Rust

if !is_leaf(&root) {
        boundary.push(root_node.borrow().val); // add root if not leaf
    }

Tree with only left subtree

Left boundary and leaves are added correctly, right boundary is empty

DSA Rust

add_right_boundary(&root_node.borrow().right, &mut boundary);

Tree with only right subtree

Right boundary and leaves are added correctly, left boundary is empty

DSA Rust

add_left_boundary(&root_node.borrow().left, &mut boundary);

When to Use This Pattern

When asked to print the outer edge nodes of a binary tree in a specific order, use boundary traversal to collect left edge, leaves, and right edge separately to avoid duplicates.

Common Mistakes

Mistake: Including leaf nodes twice by adding them in both left/right boundary and leaves
Fix: Exclude leaf nodes when adding left and right boundaries, add leaves separately

Mistake: Adding right boundary top-down instead of bottom-up
Fix: Use a stack to collect right boundary nodes and add them in reverse order

Summary

Prints the outer boundary nodes of a binary tree in order: left boundary, leaves, right boundary.

Use when you need to visit the perimeter nodes of a tree without duplicates.

Remember to exclude leaves from left and right boundaries and add right boundary bottom-up.

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