Tree Traversal Postorder Left Right Root in DSA C++ - Interactive Practice

Practice - 5 Tasks

1fill in blank

easy

Complete the code to call the postorder traversal function recursively on the left child.

DSA C++

void postorder(Node* root) {
    if (root == nullptr) return;
    postorder(root->[1]);
    // Continue traversal
}

Drag options to blanks, or click blank then click option'

Aright

Bchild

Cparent

Dleft

Attempts:

3 left

💡 Hint

Common Mistakes

Calling postorder on root->right first.

Calling postorder on root->parent which does not exist.

Using an incorrect pointer name.

In postorder traversal, we first visit the left subtree, so we call postorder on root->left.

2fill in blank

medium

Complete the code to call the postorder traversal function recursively on the right child.

DSA C++

void postorder(Node* root) {
    if (root == nullptr) return;
    postorder(root->left);
    postorder(root->[1]);
    // Continue traversal
}

Drag options to blanks, or click blank then click option'

Aright

Bparent

Cchild

Droot

Attempts:

3 left

💡 Hint

Common Mistakes

Calling postorder on root->left again.

Using root->parent which is not part of traversal.

Using an invalid pointer name.

In postorder traversal, after visiting the left subtree, we visit the right subtree by calling postorder on root->right.

3fill in blank

hard

Fix the error in the code to print the root node's value after traversing left and right subtrees.

DSA C++

void postorder(Node* root) {
    if (root == nullptr) return;
    postorder(root->left);
    postorder(root->right);
    std::cout << root->[1] << " ";
}

Drag options to blanks, or click blank then click option'

Aright

Bleft

Cdata

Dvalue

Attempts:

3 left

💡 Hint

Common Mistakes

Printing root->left or root->right which are pointers.

Using root->value which may not exist.

Forgetting to print the root node.

The root node's data is stored in the 'data' member, so we print root->data after traversing children.

4fill in blank

hard

Fill both blanks to complete the postorder traversal function that returns a vector of node values.

DSA C++

void postorder(Node* root, std::vector<int>& result) {
    if (root == nullptr) return;
    postorder(root->[1], result);
    postorder(root->[2], result);
    result.push_back(root->data);
}

Drag options to blanks, or click blank then click option'

Aleft

Bright

Cparent

Dchild

Attempts:

3 left

💡 Hint

Common Mistakes

Swapping left and right child pointers.

Using 'parent' or 'child' which are invalid pointers.

Forgetting to pass 'result' vector.

Postorder visits left child first, then right child, so blanks are 'left' and 'right'.

5fill in blank

hard

Fill all three blanks to create a postorder traversal that returns a map from node data to its depth in the tree.

DSA C++

void postorder(Node* root, std::map<int, int>& depthMap, int depth) {
    if (root == nullptr) return;
    postorder(root->[1], depthMap, depth + 1);
    postorder(root->[2], depthMap, depth + 1);
    depthMap[root->[3]] = depth;
}

Drag options to blanks, or click blank then click option'

Aleft

Bright

Cdata

Dvalue

Attempts:

3 left

💡 Hint

Common Mistakes

Using 'value' instead of 'data' for node value.

Swapping left and right pointers.

Not incrementing depth correctly.

Traverse left and right children first, then map root->data to current depth.

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