Tree Traversal Postorder Left Right Root in DSA Rust - Build from Scratch

Tree Traversal Postorder Left Right Root

📖 Scenario: You are working with a simple family tree where each person can have up to two children. You want to visit all family members in a special order: first the left child, then the right child, and finally the parent. This order is called postorder traversal.

🎯 Goal: Build a Rust program that creates a small tree of family members and prints their names in postorder (left, right, root) order.

📋 What You'll Learn

Create a binary tree node struct called Node with a name field and optional left and right children.

Create a tree with exactly three nodes: root named "Grandparent", left child named "Parent", and right child named "Uncle".

Write a recursive function called postorder_traversal that visits nodes in left, right, root order and collects their names.

Print the names collected by postorder_traversal separated by arrows (->).

💡 Why This Matters

🌍 Real World

Tree traversal is used in many real-world applications like file system navigation, expression evaluation, and organizing hierarchical data.

💼 Career

Understanding tree traversal is essential for software developers working with data structures, algorithms, and systems that manage hierarchical information.

1

Create the tree nodes

Create a struct called Node with a name field of type String, and two optional children fields called left and right of type Option>. Then create three nodes: grandparent with name "Grandparent", parent with name "Parent", and uncle with name "Uncle". Set parent and uncle as children of grandparent.

DSA Rust

// Define Node struct and create grandparent, parent, uncle nodes
// Your code here

Hint

Use Option> for children to allow empty or present child nodes. Use String::from to create names.

2

Create a vector to collect names

Inside main, create a mutable vector called names of type Vec to store the names of nodes visited during traversal.

DSA Rust

struct Node {
    name: String,
    left: Option>,
    right: Option>,
}

fn main() {
    let parent = Node {
        name: String::from("Parent"),
        left: None,
        right: None,
    };
    let uncle = Node {
        name: String::from("Uncle"),
        left: None,
        right: None,
    };
    let grandparent = Node {
        name: String::from("Grandparent"),
        left: Some(Box::new(parent)),
        right: Some(Box::new(uncle)),
    };

    // Create a mutable vector called names to store visited node names
    // Your code here
}

Hint

Use let mut names: Vec = Vec::new(); to create an empty vector that can change.

3

Write the postorder traversal function

Write a recursive function called postorder_traversal that takes a reference to a Node and a mutable reference to a Vec. It should visit the left child first, then the right child, and finally add the current node's name to the vector.

DSA Rust

struct Node {
    name: String,
    left: Option>,
    right: Option>,
}

fn main() {
    let parent = Node {
        name: String::from("Parent"),
        left: None,
        right: None,
    };
    let uncle = Node {
        name: String::from("Uncle"),
        left: None,
        right: None,
    };
    let grandparent = Node {
        name: String::from("Grandparent"),
        left: Some(Box::new(parent)),
        right: Some(Box::new(uncle)),
    };

    let mut names: Vec = Vec::new();

    // Define postorder_traversal function here
    // Your code here
}

Hint

Use if let Some(child) = &node.left to check and recurse on children. Add the current node's name after visiting children.

4

Print the postorder traversal result

Print the contents of the names vector joined by " -> " to show the postorder traversal sequence.

DSA Rust

struct Node {
    name: String,
    left: Option>,
    right: Option>,
}

fn postorder_traversal(node: &Node, names: &mut Vec) {
    if let Some(left_child) = &node.left {
        postorder_traversal(left_child, names);
    }
    if let Some(right_child) = &node.right {
        postorder_traversal(right_child, names);
    }
    names.push(node.name.clone());
}

fn main() {
    let parent = Node {
        name: String::from("Parent"),
        left: None,
        right: None,
    };
    let uncle = Node {
        name: String::from("Uncle"),
        left: None,
        right: None,
    };
    let grandparent = Node {
        name: String::from("Grandparent"),
        left: Some(Box::new(parent)),
        right: Some(Box::new(uncle)),
    };

    let mut names: Vec = Vec::new();

    postorder_traversal(&grandparent, &mut names);

    // Print the names joined by " -> "
    // Your code here
}

Hint

Use println!("{}", names.join(" -> ")); to print the vector elements joined by arrows.

Practice

1. What is the order of nodes visited in a postorder traversal of a binary tree?

easy

A. Left subtree, Right subtree, Root node

B. Root node, Left subtree, Right subtree

C. Root node, Right subtree, Left subtree

D. Right subtree, Left subtree, Root node

Solution

1. Step 1: Understand postorder traversal definition

   Postorder traversal visits nodes in the order: left subtree first, then right subtree, and finally the root node.

2. Step 2: Match the order with options

   Left subtree, Right subtree, Root node matches this order exactly: Left subtree, Right subtree, Root node.

3. Final Answer:

   Left subtree, Right subtree, Root node -> Option A

4. Quick Check:

   Postorder = Left, Right, Root [OK]

Hint: Remember postorder ends with root after children [OK]

Common Mistakes:

• Confusing postorder with preorder or inorder
• Visiting root before children
• Swapping left and right subtree order

2. Which of the following Rust function signatures correctly represents a recursive postorder traversal function for a binary tree node defined as struct Node { left: Option, right: Option, value: i32 }?

easy

A. fn postorder(node: &Option) { /* visit left, right, root */ }

B. fn postorder(node: Node) { /* visit root, left, right */ }

C. fn postorder(node: &Node) -> i32 { /* visit root only */ }

D. fn postorder(node: &mut Node) -> bool { /* visit right, left, root */ }

Solution

1. Step 1: Identify correct parameter type for recursion

   Postorder traversal usually takes a reference to an optional boxed node to handle empty children safely.

2. Step 2: Match function signature with traversal order and parameter

   fn postorder(node: &Option) { /* visit left, right, root */ } uses &Option which is correct for recursive calls and mentions visiting left, right, root.

3. Final Answer:

   fn postorder(node: &Option) { /* visit left, right, root */ } -> Option A

4. Quick Check:

   Use &Option for safe recursion [OK]

Hint: Use &Option for recursive tree traversal [OK]

Common Mistakes:

• Passing ownership instead of reference
• Returning incorrect types
• Wrong traversal order in comments

3. Given the following Rust code for postorder traversal, what will be printed?

struct Node {
    value: i32,
    left: Option,
    right: Option,
}

fn postorder(node: &Option) {
    if let Some(n) = node {
        postorder(&n.left);
        postorder(&n.right);
        print!("{} ", n.value);
    }
}

fn main() {
    let tree = Some(Box::new(Node {
        value: 1,
        left: Some(Box::new(Node {
            value: 2,
            left: None,
            right: None,
        })),
        right: Some(Box::new(Node {
            value: 3,
            left: None,
            right: None,
        })),
    }));
    postorder(&tree);
}

medium

A. 1 3 2

B. 1 2 3

C. 3 2 1

D. 2 3 1

Solution

1. Step 1: Trace postorder traversal on given tree

   The tree root is 1, left child 2, right child 3. Postorder visits left (2), right (3), then root (1).

2. Step 2: Confirm printed order

   Values printed in order: 2, then 3, then 1, matching 2 3 1 .

3. Final Answer:

   2 3 1 -> Option D

4. Quick Check:

   Postorder prints left, right, root = 2 3 1 [OK]

Hint: Print order matches left-right-root traversal [OK]

Common Mistakes:

• Confusing preorder or inorder output
• Missing spaces in print output
• Ignoring None children

4. The following Rust code attempts a postorder traversal but has a bug. What is the error?

fn postorder(node: &Option) {
    if let Some(n) = node {
        print!("{} ", n.value);
        postorder(&n.left);
        postorder(&n.right);
    }
}

medium

A. It causes a stack overflow due to infinite recursion

B. It prints root before children, not postorder

C. It does not handle None nodes correctly

D. It borrows node mutably but parameter is immutable

Solution

1. Step 1: Analyze print statement position

   The print happens before recursive calls to left and right children, so root is printed first.

2. Step 2: Compare with postorder definition

   Postorder requires visiting left and right children before root, so this order is incorrect.

3. Final Answer:

   It prints root before children, not postorder -> Option B

4. Quick Check:

   Print after children for postorder [OK]

Hint: Print root after children for correct postorder [OK]

Common Mistakes:

• Printing root before recursive calls
• Confusing preorder with postorder
• Ignoring None checks

5. You want to collect all node values of a binary tree in postorder traversal into a vector in Rust. Which of the following code snippets correctly implements this?

hard

A. fn postorder_collect(node: &Option) -> Vec<i32> {
let mut vals = Vec::new();
if let Some(n) = node {
vals.push(n.value);
vals.extend(postorder_collect(&n.left));
vals.extend(postorder_collect(&n.right));
}
vals
}

B. fn postorder_collect(node: &Option, vals: &mut Vec<i32>) {
if let Some(n) = node {
vals.push(n.value);
postorder_collect(&n.left, vals);
postorder_collect(&n.right, vals);
}
}

C. fn postorder_collect(node: &Option) -> Vec<i32> {
let mut vals = Vec::new();
if let Some(n) = node {
vals.extend(postorder_collect(&n.left));
vals.extend(postorder_collect(&n.right));
vals.push(n.value);
}
vals
}

D. fn postorder_collect(node: &Option, vals: &mut Vec<i32>) {
if let Some(n) = node {
postorder_collect(&n.right, vals);
postorder_collect(&n.left, vals);
vals.push(n.value);
}
}

Solution

1. Step 1: Understand postorder collection logic

   Postorder means collect left subtree values, then right subtree values, then root value.

2. Step 2: Check each code snippet for correct order and return type

   fn postorder_collect(node: &Option) -> Vec<i32> { let mut vals = Vec::new(); if let Some(n) = node { vals.extend(postorder_collect(&n.left)); vals.extend(postorder_collect(&n.right)); vals.push(n.value); } vals } correctly collects left and right subtree vectors first, then pushes root value, returning the combined vector.

3. Final Answer:

   fn postorder_collect(node: &Option) -> Vec<i32> { let mut vals = Vec::new(); if let Some(n) = node { vals.extend(postorder_collect(&n.left)); vals.extend(postorder_collect(&n.right)); vals.push(n.value); } vals } -> Option C

4. Quick Check:

   Collect left, right, then root in vector [OK]

Hint: Collect children first, then push root value [OK]

Common Mistakes:

• Pushing root before children
• Not returning combined vector
• Using mutable vector incorrectly