Tree Traversal Postorder Left Right Root in DSA C - Practice Problems & Challenges

Challenge - 5 Problems

❓ Predict Output

intermediate

What is the output of the postorder traversal?

Given the binary tree below, what is the postorder traversal output (Left, Right, Root)?

DSA C

/* Tree structure:
       1
      / \
     2   3
    / \
   4   5
*/

void postorder(int* arr, int index, int size) {
    if (index >= size || arr[index] == -1) return;
    postorder(arr, 2*index + 1, size); // left
    postorder(arr, 2*index + 2, size); // right
    printf("%d ", arr[index]);
}

int main() {
    int tree[] = {1, 2, 3, 4, 5};
    int size = sizeof(tree)/sizeof(tree[0]);
    postorder(tree, 0, size);
    return 0;
}

A 4 2 5 3 1

B 1 2 3 4 5

C 2 4 5 3 1

D 4 5 2 3 1

💡 Hint

Remember postorder means visit left subtree, then right subtree, then root node.

Postorder traversal visits nodes in the order: left child, right child, then the node itself.

For the given tree, the traversal is: 4 (left of 2), 5 (right of 2), 2 (root of left subtree), 3 (right child of root), 1 (root).

❓ Predict Output

intermediate

What is the postorder traversal output of this tree?

Consider this binary tree represented as an array with -1 for missing nodes: /* Tree structure: 10 / \ 5 15 \ \ 7 20 */ What is the postorder traversal output?

DSA C

void postorder(int* arr, int index, int size) {
    if (index >= size || arr[index] == -1) return;
    postorder(arr, 2*index + 1, size);
    postorder(arr, 2*index + 2, size);
    printf("%d ", arr[index]);
}

int main() {
    int tree[] = {10, 5, 15, -1, 7, -1, 20};
    int size = sizeof(tree)/sizeof(tree[0]);
    postorder(tree, 0, size);
    return 0;
}

A 7 5 20 15 10

B 5 7 15 20 10

C 5 7 20 15 10

D 7 5 15 20 10

💡 Hint

Check carefully the positions of -1 which represent missing nodes.

Postorder visits left, then right, then root.

Left subtree of 10: nodes 5 and 7 (7 is right child of 5).

Right subtree of 10: nodes 15 and 20 (20 is right child of 15).

Traversal: 7 (left subtree right child), 5 (left subtree root), 20 (right subtree right child), 15 (right subtree root), 10 (root).

🔧 Debug

advanced

Why does this postorder traversal code cause a runtime error?

Analyze the following code snippet for postorder traversal of a binary tree stored in an array. Why does it cause a runtime error?

DSA C

void postorder(int* arr, int index, int size) {
    if (arr[index] == -1) return;
    postorder(arr, 2*index + 1, size);
    postorder(arr, 2*index + 2, size);
    printf("%d ", arr[index]);
}

int main() {
    int tree[] = {1, 2, 3, 4, 5};
    int size = sizeof(tree)/sizeof(tree[0]);
    postorder(tree, 0, size);
    return 0;
}

A The code uses -1 to mark missing nodes but does not handle them properly in the traversal order.

B The code accesses arr[index] without checking if index is within bounds, causing out-of-bounds access.

C The printf statement is missing a newline causing output buffering issues.

D The recursion does not stop because the base case is incorrect; it should check for index == size.

💡 Hint

Check the order of conditions in the base case.

The function checks arr[index] == -1 before verifying if index is within the array bounds.

If index is out of bounds, accessing arr[index] causes a runtime error.

Correct approach is to check index >= size before accessing arr[index].

🧠 Conceptual

advanced

Which property is true for postorder traversal of a binary tree?

Select the correct statement about postorder traversal (Left, Right, Root) of a binary tree.

A The root node is visited after all its left and right subtree nodes have been visited.

B The traversal visits all left subtree nodes before any right subtree nodes.

C The root node is always visited before its children.

D Postorder traversal visits nodes in the order Root, Left, Right.

💡 Hint

Think about when the root node is printed in postorder.

Postorder traversal visits left subtree, then right subtree, then the root node last.

So the root is visited after all its children.

❓ Predict Output

expert

What is the postorder traversal output of this complex tree?

Given the following binary tree represented as an array with -1 for missing nodes, what is the postorder traversal output?

DSA C

void postorder(int* arr, int index, int size) {
    if (index >= size || arr[index] == -1) return;
    postorder(arr, 2*index + 1, size);
    postorder(arr, 2*index + 2, size);
    printf("%d ", arr[index]);
}

int main() {
    int tree[] = {8, 3, 10, 1, 6, -1, 14, -1, -1, 4, 7, -1, -1, 13, -1};
    int size = sizeof(tree)/sizeof(tree[0]);
    postorder(tree, 0, size);
    return 0;
}

A 1 7 4 6 3 13 14 10 8

B 1 6 4 7 3 13 14 10 8

C 1 4 7 6 3 13 14 10 8

D 1 4 7 6 3 14 13 10 8

💡 Hint

Carefully follow left, then right, then root for each subtree, considering -1 as missing nodes.

Traverse left subtree of 8: nodes 3, 1, 6, 4, 7.

Traverse right subtree of 8: nodes 10, 14, 13.

Postorder visits left subtree nodes first (1 4 7 6 3), then right subtree nodes (13 14 10), then root (8).

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