Tree Traversal Postorder Left Right Root in DSA Rust

Mental Model

Visit the left child, then the right child, and finally the node itself. This order ensures children are processed before their parent.

Analogy: Imagine cleaning a tree house: first clean the left room, then the right room, and only after both are clean, clean the main hall.

    1
   / \
  2   3
 / \
4   5

↑ root at 1

Dry Run Walkthrough

Input: Tree: 1 with left child 2 and right child 3; 2 has children 4 (left) and 5 (right)

Goal: Print nodes in postorder: left subtree, right subtree, then root

Step 1: Visit left subtree of 1 (node 2)

Current node: 2
Traverse left child 4

Why: Postorder requires left subtree first

Step 2: Visit left child 4 (leaf), print 4

4 (printed)
Back to node 2

Why: Leaf node has no children, print it now

Step 3: Visit right child 5 of node 2, print 5

4 -> 5 (printed)
Back to node 2

Why: Right subtree after left subtree

Step 4: Print node 2 after its children

4 -> 5 -> 2 (printed)
Back to root 1

Why: Root printed after children

Step 5: Visit right subtree of 1 (node 3), print 3

4 -> 5 -> 2 -> 3 (printed)
Back to root 1

Why: Right subtree after left subtree

Step 6: Print root node 1 last

4 -> 5 -> 2 -> 3 -> 1 (printed)

Why: Root printed after both subtrees

Result:

4 -> 5 -> 2 -> 3 -> 1 -> null

Annotated Code

DSA Rust

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

#[derive(Debug)]
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 postorder_traversal(root: Option<Rc<RefCell<TreeNode>>>, result: &mut Vec<i32>) {
    if let Some(node_rc) = root {
        let node = node_rc.borrow();
        postorder_traversal(node.left.clone(), result); // traverse left subtree
        postorder_traversal(node.right.clone(), result); // traverse right subtree
        result.push(node.val); // visit root
    }
}

fn main() {
    // Build tree:
    //     1
    //    / \
    //   2   3
    //  / \
    // 4   5
    let root = TreeNode::new(1);
    let node2 = TreeNode::new(2);
    let node3 = TreeNode::new(3);
    let node4 = TreeNode::new(4);
    let node5 = TreeNode::new(5);

    root.borrow_mut().left = Some(node2.clone());
    root.borrow_mut().right = Some(node3.clone());
    node2.borrow_mut().left = Some(node4.clone());
    node2.borrow_mut().right = Some(node5.clone());

    let mut result = Vec::new();
    postorder_traversal(Some(root), &mut result);

    // Print result in requested format
    for val in &result {
        print!("{} -> ", val);
    }
    println!("null");
}

postorder_traversal(node.left.clone(), result); // traverse left subtree

advance to left child first to process left subtree

postorder_traversal(node.right.clone(), result); // traverse right subtree

then advance to right child to process right subtree

result.push(node.val); // visit root

visit current node after children are processed

Output

4 -> 5 -> 2 -> 3 -> 1 -> null

Complexity Analysis

Time: O(n) because each node is visited exactly once

Space: O(h) where h is tree height due to recursion stack

vs Alternative: Compared to iterative traversal, recursive postorder is simpler but uses call stack; iterative may use explicit stack with similar time

Edge Cases

Empty tree (root is None)

No nodes visited, result is empty

DSA Rust

if let Some(node_rc) = root {

Single node tree

Only root node is visited and printed

DSA Rust

if let Some(node_rc) = root {

Tree with only left children

Nodes visited from bottom left up to root in postorder

DSA Rust

postorder_traversal(node.left.clone(), result);

When to Use This Pattern

When a problem asks to process children before their parent in a tree, use postorder traversal to visit left, right, then root nodes.

Common Mistakes

Mistake: Visiting root before children (preorder) instead of after
Fix: Change order to visit left subtree, then right subtree, then root

Mistake: Visiting right subtree before left subtree
Fix: Always visit left subtree first, then right subtree

Summary

Postorder traversal visits left child, then right child, then the node itself.

Use it when you need to process children before their parent, like deleting a tree.

The key insight is that the root is visited last after both subtrees.

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