Tree Traversal Postorder Left Right Root in DSA C++ - 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 program that creates a small binary tree, sets up a function to traverse it in postorder (left, right, root), and prints the values in the correct order.

📋 What You'll Learn

Create a binary tree with exactly 3 nodes: root with value 1, left child with value 2, right child with value 3

Create a function called postorderTraversal that visits nodes in left-right-root order

Use recursion inside postorderTraversal to visit left child, then right child, then print the current node's value

Print the values of the nodes in the order they are visited by postorderTraversal

💡 Why This Matters

🌍 Real World

Postorder traversal is used in file system operations, expression tree evaluations, and cleanup tasks where children must be handled before parents.

💼 Career

Understanding tree traversals is essential for software engineers working with hierarchical data, compilers, databases, and many algorithms.

1

Create the binary tree nodes

Create a struct called Node with an int value and two pointers called left and right. Then create three nodes: root with value 1, root->left with value 2, and root->right with value 3.

DSA C++

// Define struct Node and create root, root->left, root->right nodes
// Your code here

Hint

Start by defining the Node structure with value and pointers to left and right children. Then create the root node and assign its left and right children.

2

Create the postorder traversal function

Write a function called postorderTraversal that takes a Node* parameter called node. Inside the function, first check if node is nullptr. If it is, return immediately. Otherwise, call postorderTraversal recursively on node->left, then on node->right.

DSA C++

void postorderTraversal(Node* node) {
    // Your code here
}

Hint

Use recursion to visit the left child first, then the right child. Remember to stop if the node is nullptr.

3

Print the node value after visiting children

Inside the postorderTraversal function, after the recursive calls to postorderTraversal(node->left) and postorderTraversal(node->right), add a line to print the current node's value using std::cout followed by a space.

DSA C++

void postorderTraversal(Node* node) {
    if (node == nullptr) {
        return;
    }
    postorderTraversal(node->left);
    postorderTraversal(node->right);
    // Your code here
}

Hint

After visiting left and right children, print the current node's value with a space to separate values.

4

Call the traversal and print the result

In the main function, call postorderTraversal(root) to start the traversal from the root. Then print a newline using std::cout.

DSA C++

int main() {
    // Call postorderTraversal with root
    // Print a newline
    // Your code here
    return 0;
}

Hint

Call the traversal starting from root and print a newline after to see the output clearly.

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