Tree Traversal Postorder Left Right Root in DSA C

Mental Model

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

Analogy: Imagine cleaning a treehouse: 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

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: move to node 2

1 -> [curr->2] -> 3
2 -> 4 -> 5
↑ exploring left subtree

Why: Postorder starts with left subtree

Step 2: Visit left subtree of 2: move to node 4

2 -> [curr->4] -> 5
4 has no children
↑ at leftmost leaf

Why: Keep going left until leaf

Step 3: Print node 4 (left leaf)

Printed: 4
Back to node 2

Why: Left child processed before parent

Step 4: Visit right subtree of 2: move to node 5

2 -> 4 -> [curr->5]
5 has no children
↑ at right leaf

Why: Process right child after left

Step 5: Print node 5 (right leaf)

Printed: 4 5
Back to node 2

Why: Right child processed before parent

Step 6: Print node 2 (parent after children)

Printed: 4 5 2
Back to root 1

Why: Parent printed after children

Step 7: Visit right subtree of 1: move to node 3

1 -> 2 -> [curr->3]
3 has no children
↑ at right child of root

Why: Process right subtree after left

Step 8: Print node 3 (right child)

Printed: 4 5 2 3
Back to root 1

Why: Right subtree done before root

Step 9: Print node 1 (root last)

Printed: 4 5 2 3 1
Traversal complete

Why: Root printed after both subtrees

Result:

4 5 2 3 1

Annotated Code

DSA C

#include <stdio.h>
#include <stdlib.h>

// Define tree node structure
typedef struct Node {
    int data;
    struct Node* left;
    struct Node* right;
} Node;

// Create new node
Node* newNode(int data) {
    Node* node = (Node*)malloc(sizeof(Node));
    node->data = data;
    node->left = NULL;
    node->right = NULL;
    return node;
}

// Postorder traversal: left, right, root
void postorder(Node* root) {
    if (root == NULL) return; // base case: empty subtree

    postorder(root->left);  // traverse left subtree
    postorder(root->right); // traverse right subtree
    printf("%d ", root->data); // visit root node
}

int main() {
    // Build tree from dry run example
    Node* root = newNode(1);
    root->left = newNode(2);
    root->right = newNode(3);
    root->left->left = newNode(4);
    root->left->right = newNode(5);

    postorder(root);
    printf("\n");
    return 0;
}

if (root == NULL) return;

stop recursion when subtree is empty

postorder(root->left);

traverse left subtree first

postorder(root->right);

then traverse right subtree

printf("%d ", root->data);

visit root node after children

Output

4 5 2 3 1 

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 NULL)

Function returns immediately without printing

DSA C

if (root == NULL) return;

Single node tree

Prints the single node value

DSA C

if (root == NULL) return;

Tree with only left or only right children

Traverses existing children correctly before printing parent

DSA C

postorder(root->left); postorder(root->right);

When to Use This Pattern

When a problem requires processing children before their parent, especially in trees, use postorder traversal to ensure bottom-up processing.

Common Mistakes

Mistake: Printing the root node before traversing children (preorder instead of postorder)
Fix: Move the print statement after recursive calls to left and right children

Summary

Visits left subtree, then right subtree, then the root node.

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

The key is to print the node only after both subtrees are fully processed.

Practice

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

easy

A. Right subtree, Left subtree, Root node

B. Root node, Left subtree, Right subtree

C. Root node, Right subtree, Left subtree

D. Left subtree, Right subtree, Root node

Solution

1. Step 1: Understand postorder traversal definition

   Postorder traversal visits the left subtree first, then the right subtree, and finally the root node.

2. Step 2: Apply the order to the traversal

   Following this order ensures all children are visited before the parent node.

3. Final Answer:

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

4. Quick Check:

   Postorder = Left, Right, Root [OK]

Hint: Remember: postorder ends with the root node [OK]

Common Mistakes:

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

2. Which of the following C code snippets correctly implements the postorder traversal function for a binary tree node struct Node?

easy

A. void postorder(struct Node* root) { if(root) { printf("%d ", root->data); postorder(root->left); postorder(root->right); } }

B. void postorder(struct Node* root) { if(root) { postorder(root->left); postorder(root->right); printf("%d ", root->data); } }

C. void postorder(struct Node* root) { if(root) { postorder(root->right); postorder(root->left); printf("%d ", root->data); } }

D. void postorder(struct Node* root) { if(root) { postorder(root->left); printf("%d ", root->data); postorder(root->right); } }

Solution

1. Step 1: Check traversal order in code

   Postorder requires visiting left subtree, then right subtree, then root node.

2. Step 2: Match code to postorder steps

   void postorder(struct Node* root) { if(root) { postorder(root->left); postorder(root->right); printf("%d ", root->data); } } calls postorder on left, then right, then prints root data, matching postorder.

3. Final Answer:

   Correct postorder traversal code -> Option B

4. Quick Check:

   Left, Right, Root in code = void postorder(struct Node* root) { if(root) { postorder(root->left); postorder(root->right); printf("%d ", root->data); } } [OK]

Hint: Print root after left and right recursive calls [OK]

Common Mistakes:

• Printing root before children (preorder)
• Swapping left and right subtree calls
• Missing null check for root

3. Given the binary tree below:

    1
   / \
  2   3
 / \
4   5

What is the output of a postorder traversal?

medium

A. 2 4 5 3 1

B. 1 2 4 5 3

C. 4 5 2 3 1

D. 4 2 5 3 1

Solution

1. Step 1: Traverse left subtree of root (1)

   Left subtree rooted at 2: postorder visits 4, then 5, then 2.

2. Step 2: Traverse right subtree and root

   Right subtree is 3 (leaf), then visit root 1 last.

3. Final Answer:

   4 5 2 3 1 -> Option C

4. Quick Check:

   Left, Right, Root = 4 5 2 3 1 [OK]

Hint: Visit children fully before printing parent [OK]

Common Mistakes:

• Printing root too early
• Mixing left and right subtree order
• Confusing preorder or inorder output

4. Consider the following C function for postorder traversal:

void postorder(struct Node* root) {
    if(root == NULL) return;
    postorder(root->right);
    postorder(root->left);
    printf("%d ", root->data);
}

What is the main issue with this code?

medium

A. It visits the right subtree before the left subtree, reversing the correct order

B. It does not check if root is NULL before recursion

C. It prints the root before visiting children

D. It causes infinite recursion

Solution

1. Step 1: Analyze the order of recursive calls

   The code calls postorder on right subtree first, then left subtree, which reverses the expected left-right order.

2. Step 2: Check printing position

   Printing root after children is correct, but subtree order is wrong.

3. Final Answer:

   Visits right subtree before left, reversing order -> Option A

4. Quick Check:

   Left before right needed, code does right before left [OK]

Hint: Left subtree call must come before right subtree call [OK]

Common Mistakes:

• Swapping left and right subtree calls
• Printing root too early
• Missing null check (not in this code though)

5. You have a binary tree where each node stores an integer. You want to collect all node values in postorder traversal into an array. Which approach correctly achieves this?

hard

A. Use recursion: traverse left subtree, traverse right subtree, then append root value to array

B. Use recursion: append root value, then traverse left and right subtrees

C. Use a queue to enqueue root first, then left and right children

D. Traverse the tree level by level and append nodes to array

Solution

1. Step 1: Understand postorder traversal for collection

   Postorder means visiting left subtree, right subtree, then root, so values must be appended in that order.

2. Step 2: Choose correct method to collect values

   Recursion that appends root after children ensures correct postorder sequence in the array.

3. Final Answer:

   Recursion: left, right, then append root -> Option A

4. Quick Check:

   Append after children = postorder collection [OK]

Hint: Append root after children for postorder array [OK]

Common Mistakes:

• Appending root before children (preorder)
• Using queue for level order, not postorder
• Confusing traversal types