Tree Traversal Postorder Left Right Root in DSA C++

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: Go to left child of 1 (node 2)

1 -> [curr->2] -> 3
2 -> 4 -> 5
↑ at node 2

Why: Start with left subtree to follow postorder

Step 2: Go to left child of 2 (node 4)

1 -> 2 -> 3
2 -> [curr->4] -> 5
↑ at node 4

Why: Keep going left to reach leftmost node

Step 3: Node 4 has no children, print 4

Printed: 4
Back to node 2

Why: Left subtree done, print leaf node

Step 4: Go to right child of 2 (node 5)

1 -> 2 -> 3
2 -> 4 -> [curr->5]
↑ at node 5

Why: Now process right subtree of node 2

Step 5: Node 5 has no children, print 5

Printed: 4 5
Back to node 2

Why: Right subtree done, print leaf node

Step 6: Print node 2 after its children

Printed: 4 5 2
Back to node 1

Why: Both children processed, print parent

Step 7: Go to right child of 1 (node 3)

1 -> [curr->3]
↑ at node 3

Why: Process right subtree of root

Step 8: Node 3 has no children, print 3

Printed: 4 5 2 3
Back to node 1

Why: Right subtree done, print leaf node

Step 9: Print root node 1 last

Printed: 4 5 2 3 1

Why: Root printed after all children

Result:

4 5 2 3 1

Annotated Code

DSA C++

#include <iostream>
using namespace std;

struct Node {
    int val;
    Node* left;
    Node* right;
    Node(int v) : val(v), left(nullptr), right(nullptr) {}
};

void postorder(Node* root) {
    if (root == nullptr) return; // base case: empty node
    postorder(root->left); // visit left subtree
    postorder(root->right); // visit right subtree
    cout << root->val << " "; // visit root last
}

int main() {
    // Build tree:
    //     1
    //    / \
    //   2   3
    //  / \
    // 4   5
    Node* root = new Node(1);
    root->left = new Node(2);
    root->right = new Node(3);
    root->left->left = new Node(4);
    root->left->right = new Node(5);

    postorder(root);
    cout << endl;
    return 0;
}

if (root == nullptr) return;

stop recursion at empty node

postorder(root->left);

traverse left subtree first

postorder(root->right);

then traverse right subtree

cout << root->val << " ";

print current 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 uses explicit stack but can be more complex

Edge Cases

Empty tree (root is nullptr)

Function returns immediately without printing

DSA C++

if (root == nullptr) return;

Single node tree

Prints the single node value

DSA C++

if (root == nullptr) return;

Tree with only left children

Visits all left nodes in order, printing from bottom up

DSA C++

postorder(root->left);

When to Use This Pattern

When you need to process children before their parent, especially in cleanup or evaluation problems, use postorder traversal.

Common Mistakes

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

Summary

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

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

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

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 traversal order to options

   Left subtree, Right subtree, Root node correctly lists the order as Left, Right, Root which matches postorder traversal.

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
• Swapping left and right subtree order
• Thinking root is visited first

2. Which of the following C++ function signatures correctly represents a postorder traversal of a binary tree node Node*?

easy

A. void postorder(Node* root) { visit(root); postorder(root->left); postorder(root->right); }

B. void postorder(Node* root) { postorder(root->right); postorder(root->left); visit(root); }

C. void postorder(Node* root) { postorder(root->right); visit(root); postorder(root->left); }

D. void postorder(Node* root) { postorder(root->left); postorder(root->right); visit(root); }

Solution

1. Step 1: Recall postorder traversal steps

   Postorder visits left subtree, then right subtree, then root node.

2. Step 2: Check function calls order

   void postorder(Node* root) { postorder(root->left); postorder(root->right); visit(root); } calls postorder on left, then right, then visits root, matching postorder traversal.

3. Final Answer:

   void postorder(Node* root) { postorder(root->left); postorder(root->right); visit(root); } -> Option D

4. Quick Check:

   Left, Right, Root call order = void postorder(Node* root) { postorder(root->left); postorder(root->right); visit(root); } [OK]

Hint: Postorder calls left, then right, then root visit [OK]

Common Mistakes:

• Visiting root before children (preorder)
• Swapping left and right subtree calls
• Missing visit call after recursion

3. Given the binary tree:

    1
   / \
  2   3
 / \
4   5

What is the output of a postorder traversal?

medium

A. [1, 2, 3, 4, 5]

B. [4, 2, 5, 3, 1]

C. [4, 5, 2, 3, 1]

D. [2, 4, 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 alone, visited next. Finally, root 1 is visited.

3. Final Answer:

   [4, 5, 2, 3, 1] -> Option C

4. Quick Check:

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

Hint: Visit children fully before root [OK]

Common Mistakes:

• Listing root before children
• Mixing left and right subtree order
• Confusing with preorder or inorder output

4. The following C++ code attempts postorder traversal but produces incorrect output. What is the error?

void postorder(Node* root) {
  if (!root) return;
  postorder(root->right);
  postorder(root->left);
  visit(root);
}

medium

A. Left and right subtree calls are swapped

B. The base case check is incorrect

C. The visit call is missing

D. The function should visit root before children

Solution

1. Step 1: Analyze recursive calls order

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

2. Step 2: Understand correct postorder order

   Postorder requires left subtree first, then right subtree, then root visit.

3. Final Answer:

   Left and right subtree calls are swapped -> Option A

4. Quick Check:

   Left before right in postorder [OK]

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

Common Mistakes:

• Swapping left and right subtree calls
• Visiting root before children
• Omitting base case check

5. You want to collect all node values of a binary tree in postorder traversal into a vector. Which code snippet correctly implements this in C++?

hard

A. void postorder(Node* root, vector<int>& res) { if (!root) return; res.push_back(root->val); postorder(root->left, res); postorder(root->right, res); }

B. void postorder(Node* root, vector<int>& res) { if (!root) return; postorder(root->left, res); postorder(root->right, res); res.push_back(root->val); }

C. void postorder(Node* root, vector<int>& res) { if (!root) return; postorder(root->right, res); postorder(root->left, res); res.push_back(root->val); }

D. void postorder(Node* root, vector<int>& res) { if (!root) return; postorder(root->left, res); res.push_back(root->val); postorder(root->right, res); }

Solution

1. Step 1: Confirm traversal order in code

   void postorder(Node* root, vector<int>& res) { if (!root) return; postorder(root->left, res); postorder(root->right, res); res.push_back(root->val); } calls postorder on left, then right subtree, then adds root value to vector, matching postorder.

2. Step 2: Check other options for order mistakes

   The other options either add the root value too early or swap left and right calls, breaking postorder.

3. Final Answer:

   void postorder(Node* root, vector<int>& res) { if (!root) return; postorder(root->left, res); postorder(root->right, res); res.push_back(root->val); } -> Option B

4. Quick Check:

   Left, Right, Root push_back order = void postorder(Node* root, vector<int>& res) { if (!root) return; postorder(root->left, res); postorder(root->right, res); res.push_back(root->val); } [OK]

Hint: Push root value after left and right recursion [OK]

Common Mistakes:

• Pushing root value before children
• Swapping left and right subtree calls
• Forgetting to check for null root