Boundary Traversal of Binary Tree in DSA Rust - Deep Dive

Overview - Boundary Traversal of Binary Tree

What is it?

Boundary Traversal of a Binary Tree is a way to visit all the nodes on the outer edge of the tree. It starts from the root, then visits the left boundary top-down, all the leaf nodes left to right, and finally the right boundary bottom-up. This traversal gives a list of nodes that form the outline or boundary of the tree.

Why it matters

Without boundary traversal, we might miss understanding the shape or outline of a tree, which is important in many applications like graphical rendering, tree visualization, or solving problems that need edge nodes. It helps us capture the tree's outer structure efficiently.

Where it fits

Before learning boundary traversal, you should understand basic binary trees and tree traversals like preorder, inorder, and postorder. After mastering boundary traversal, you can explore advanced tree algorithms like vertical order traversal or tree views (left, right, top).

Mental Model

Core Idea

Boundary traversal collects nodes on the tree's outer edge by combining left boundary, leaves, and right boundary in a specific order.

Think of it like...

Imagine walking around a park fence: you start at the gate (root), walk along the left side of the fence (left boundary), then walk around the bushes inside the fence (leaf nodes), and finally walk back along the right side of the fence (right boundary) to complete the loop.

          Root
         /    \
    Left       Right
   Boundary   Boundary
      |          |
  Leaf Nodes (bottom)

Traversal order:
Root -> Left Boundary (top-down) -> Leaves (left to right) -> Right Boundary (bottom-up)

Build-Up - 7 Steps

1

Foundation

Understanding Binary Tree Structure

Concept: Learn what a binary tree is and how nodes connect with left and right children.

A binary tree is a structure where each node has up to two children: left and right. The top node is called the root. Nodes without children are called leaves. Understanding this helps us know which nodes form the edges.

Result

You can identify root, internal nodes, and leaves in any binary tree.

Knowing the tree's shape and node types is essential before picking nodes for boundary traversal.

2

Foundation

Basic Tree Traversals Review

Concept: Recall preorder, inorder, and postorder traversals to understand node visiting orders.

Preorder visits root first, then left subtree, then right subtree. Inorder visits left subtree, root, then right subtree. Postorder visits left subtree, right subtree, then root. These help us understand how to visit nodes in order.

Result

You can trace how nodes are visited in different traversal orders.

Understanding traversal orders helps in designing the boundary traversal which combines specific node visits.

3

Intermediate

Identifying Left Boundary Nodes

🤔Before reading on: do you think leaf nodes are part of the left boundary? Commit to yes or no.

Concept: Left boundary nodes are all nodes on the path from root to the leftmost leaf, excluding leaves.

Start from root's left child and keep moving left if possible; if no left child, move right. Collect nodes until you reach a leaf. Do not include leaf nodes here because they will be added separately.

Result

You get a list of nodes forming the left edge from top to bottom, excluding leaves.

Separating leaves from boundary nodes avoids duplicates and keeps traversal order clean.

4

Intermediate

Collecting Leaf Nodes Left to Right

🤔Before reading on: do you think leaf nodes on the left boundary are collected twice? Commit to yes or no.

Concept: Leaf nodes are all nodes without children, collected from left subtree to right subtree.

Traverse the entire tree in a simple way (like inorder). Whenever you find a leaf node, add it to the leaf list. This includes leaves on left and right boundaries.

Result

You get a list of all leaf nodes in left-to-right order.

Collecting leaves separately ensures all edge leaves are included exactly once.

5

Intermediate

Identifying Right Boundary Nodes Bottom-Up

🤔Before reading on: do you think right boundary nodes are collected top-down or bottom-up? Commit to your answer.

Concept: Right boundary nodes are all nodes on the path from root to the rightmost leaf, excluding leaves, collected bottom-up.

Start from root's right child and keep moving right if possible; if no right child, move left. Collect nodes until you reach a leaf. Store them temporarily and reverse the order before adding to the result.

Result

You get a list of right boundary nodes from bottom to top, excluding leaves.

Reversing the right boundary nodes preserves the correct traversal order around the tree.

6

Advanced

Combining Boundaries for Full Traversal

🤔Before reading on: do you think the root node is included once or multiple times in the boundary traversal? Commit to your answer.

Concept: Combine root, left boundary, leaves, and right boundary nodes carefully to form the full boundary traversal without duplicates.

Start with root node. Add left boundary nodes (excluding leaves). Add all leaf nodes. Add right boundary nodes (excluding leaves) in bottom-up order. This order ensures a continuous boundary path.

Result

A list of nodes representing the boundary traversal of the binary tree.

Careful combination avoids duplicates and maintains the correct boundary order.

7

Expert

Efficient Rust Implementation with Safe Recursion

🤔Before reading on: do you think mutable state or passing vectors is better for collecting nodes in Rust? Commit to your answer.

Concept: Implement boundary traversal in Rust using recursive functions and mutable vectors to collect nodes efficiently and safely.

Use three recursive helper functions: one for left boundary, one for leaves, and one for right boundary. Pass mutable vectors to collect nodes. Use pattern matching to handle node options safely. Avoid duplicates by excluding leaves in boundary functions.

Result

A complete, runnable Rust code that prints boundary traversal nodes in correct order.

Understanding Rust's ownership and borrowing rules helps write safe and efficient tree traversals.

Under the Hood

Boundary traversal works by splitting the problem into three parts: left boundary, leaves, and right boundary. Each part is collected by traversing the tree in a specific way. Left boundary is collected top-down by always choosing left child first, right boundary bottom-up by choosing right child first and reversing, and leaves by visiting all nodes and checking if they have no children. This avoids duplicates and preserves order.

Why designed this way?

This design separates concerns to avoid visiting nodes multiple times and to maintain the correct order of nodes around the tree's edge. Alternatives like a single traversal with complex conditions are harder to implement and error-prone. The split approach is clear, modular, and efficient.

Root
├── Left Boundary (top-down)
│    ├── Node
│    └── ...
├── Leaves (left to right)
│    ├── Leaf Node
│    └── ...
└── Right Boundary (bottom-up)
     ├── Node
     └── ...

Myth Busters - 4 Common Misconceptions

Quick: Are leaf nodes included in both left boundary and leaf collection? Commit to yes or no.

Common Belief: Leaf nodes are part of the left and right boundaries as well as leaves, so they appear multiple times.

Reality: Leaf nodes are collected only once during the leaf collection phase, not in left or right boundaries to avoid duplicates.

Why it matters: Including leaves multiple times causes repeated nodes in the output, breaking the boundary traversal correctness.

Quick: Does boundary traversal always start with the root node? Commit to yes or no.

Common Belief: Boundary traversal can start anywhere on the tree, not necessarily the root.

Reality: Boundary traversal always starts with the root node because it is the topmost boundary node.

Why it matters: Skipping the root node leads to incomplete boundary traversal and missing the tree's top edge.

Quick: Is the right boundary collected top-down like the left boundary? Commit to yes or no.

Common Belief: Right boundary nodes are collected top-down just like left boundary nodes.

Reality: Right boundary nodes are collected bottom-up to maintain the correct traversal order around the tree.

Why it matters: Collecting right boundary top-down reverses the boundary order and breaks the traversal sequence.

Quick: Can boundary traversal be done with a single simple traversal? Commit to yes or no.

Common Belief: A single traversal can collect all boundary nodes easily without separate steps.

Reality: Boundary traversal requires separate steps for left boundary, leaves, and right boundary to avoid duplicates and maintain order.

Why it matters: Trying a single traversal often leads to complex code and incorrect node ordering.

Expert Zone

1

Left and right boundary collections exclude leaf nodes to prevent duplication with leaf collection, which is a subtle but crucial detail.

2

Right boundary nodes must be collected in a stack or reversed order because the traversal order is counterclockwise around the tree.

3

In Rust, careful use of mutable references and pattern matching avoids common ownership and borrowing pitfalls during recursive traversal.

When NOT to use

Boundary traversal is not suitable when you need all nodes or internal nodes only. For full tree data, use inorder or level order traversal. For views like top or bottom view, use specialized algorithms. Also, for very large trees, iterative or memory-optimized traversals may be better.

Production Patterns

In production, boundary traversal is used in graphical tree rendering to outline shapes, in UI frameworks to highlight edges, and in coding interviews to test understanding of tree traversal variations and recursion control.

Connections

Graph Perimeter Detection

Boundary traversal in trees is similar to finding perimeter nodes in graphs.

Understanding boundary traversal helps in algorithms that detect edges or boundaries in graph structures, useful in image processing or network analysis.

Convex Hull in Computational Geometry

Both find the outer boundary enclosing a set of points or nodes.

Knowing boundary traversal deepens understanding of how to identify outer layers or hulls in different data structures and geometric problems.

Human Visual Perception of Edges

Boundary traversal mimics how humans perceive edges and outlines in visual scenes.

This connection shows how algorithms can model natural perception processes, bridging computer science and cognitive science.

Common Pitfalls

#1 Including leaf nodes in left boundary collection causes duplicates.

Wrong approach:

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

Correct approach:

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

Root cause:

Not checking if a node is a leaf before adding it to the boundary causes duplicates.

#2 Collecting right boundary nodes top-down breaks traversal order.

Wrong approach:

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

Correct approach:

fn right_boundary(node: &Option>, res: &mut Vec) {
if let Some(n) = node {
if n.right.is_some() {
right_boundary(&n.right, res);
} else if n.left.is_some() {
right_boundary(&n.left, res);
}
if n.left.is_some() || n.right.is_some() {
res.push(n.val); // bottom-up
}
}
}

Root cause:

Not reversing the right boundary nodes causes incorrect output order.

#3 Not including the root node in the boundary traversal.

Wrong approach:

fn boundary_traversal(root: &Option>) -> Vec {
let mut res = Vec::new();
if root.is_none() {
return res;
}
// Missing root push
left_boundary(&root.as_ref().unwrap().left, &mut res);
leaves(root, &mut res);
right_boundary(&root.as_ref().unwrap().right, &mut res);
res
}

Correct approach:

fn boundary_traversal(root: &Option>) -> Vec {
let mut res = Vec::new();
if root.is_none() {
return res;
}
res.push(root.as_ref().unwrap().val); // include root
left_boundary(&root.as_ref().unwrap().left, &mut res);
leaves(root, &mut res);
right_boundary(&root.as_ref().unwrap().right, &mut res);
res
}

Root cause:

Forgetting to add the root node leads to incomplete boundary traversal.

Key Takeaways

Boundary traversal visits the outer edge nodes of a binary tree in a specific order: root, left boundary, leaves, then right boundary.

Separating left boundary, leaves, and right boundary collections avoids duplicates and preserves traversal order.

Right boundary nodes must be collected bottom-up to maintain the correct sequence around the tree.

Implementing boundary traversal requires careful recursion and checks to distinguish leaves from boundary nodes.

Understanding boundary traversal deepens knowledge of tree structure and traversal techniques, useful in many real-world applications.

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