Challenge - 5 Problems
Postorder Traversal Master
Get all challenges correct to earn this badge!
Test your skills under time pressure!
❓ Predict Output
intermediate2:00remaining
Output of Postorder Traversal on a Simple Binary Tree
What is the output of the following C++ code that performs a postorder traversal (Left, Right, Root) on the given binary tree?
DSA C++
struct Node {
int data;
Node* left;
Node* right;
Node(int val) : data(val), left(nullptr), right(nullptr) {}
};
void postorder(Node* root) {
if (!root) return;
postorder(root->left);
postorder(root->right);
std::cout << root->data << " ";
}
int main() {
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);
return 0;
}Attempts:
2 left
💡 Hint
Remember postorder means visit left subtree, then right subtree, then the root node.
✗ Incorrect
Postorder traversal visits nodes in Left, Right, Root order. For this tree, left subtree nodes 4 and 5 are visited first, then their parent 2, then right child 3, and finally root 1.
🧠 Conceptual
intermediate1:00remaining
Number of Nodes Visited in Postorder Traversal
Given a binary tree with 7 nodes, how many nodes will be visited during a complete postorder traversal?
Attempts:
2 left
💡 Hint
Postorder traversal visits every node exactly once.
✗ Incorrect
Postorder traversal visits all nodes in the tree exactly once, so the count equals the total number of nodes.
🔧 Debug
advanced2:00remaining
Identify the Bug in Postorder Traversal Code
What error will the following C++ code produce when performing postorder traversal?
DSA C++
struct Node {
int data;
Node* left;
Node* right;
Node(int val) : data(val), left(nullptr), right(nullptr) {}
};
void postorder(Node* root) {
if (root == nullptr) return;
postorder(root->right);
postorder(root->left);
std::cout << root->data << " ";
}
int main() {
Node* root = new Node(10);
root->left = new Node(20);
root->right = new Node(30);
postorder(root);
return 0;
}Attempts:
2 left
💡 Hint
Check the order of recursive calls for left and right children.
✗ Incorrect
The code visits right subtree first, then left subtree, then root, so output is 30 20 10 instead of standard postorder.
🚀 Application
advanced2:30remaining
Postorder Traversal Output for Unbalanced Tree
What is the output of postorder traversal on this unbalanced tree?
Tree structure:
- Root: 5
- Root's right child: 8
- Node 8's left child: 6
- Node 6's right child: 7
DSA C++
struct Node {
int data;
Node* left;
Node* right;
Node(int val) : data(val), left(nullptr), right(nullptr) {}
};
void postorder(Node* root) {
if (!root) return;
postorder(root->left);
postorder(root->right);
std::cout << root->data << " ";
}
int main() {
Node* root = new Node(5);
root->right = new Node(8);
root->right->left = new Node(6);
root->right->left->right = new Node(7);
postorder(root);
return 0;
}Attempts:
2 left
💡 Hint
Follow left, then right, then root order carefully for each subtree.
✗ Incorrect
Postorder visits left subtree (none for root), then right subtree (6's subtree), then root. 7 is right child of 6, so order is 7, 6, 8, 5.
🧠 Conceptual
expert3:00remaining
Postorder Traversal Stack Simulation Output
Given the iterative postorder traversal using two stacks on the tree below, what is the final printed output?
Tree:
- Root: 10
- Left child: 20
- Right child: 30
- Left child's left: 40
- Left child's right: 50
DSA C++
void postorderIterative(Node* root) {
if (!root) return;
std::stack<Node*> s1, s2;
s1.push(root);
while (!s1.empty()) {
Node* curr = s1.top(); s1.pop();
s2.push(curr);
if (curr->left) s1.push(curr->left);
if (curr->right) s1.push(curr->right);
}
while (!s2.empty()) {
std::cout << s2.top()->data << " ";
s2.pop();
}
}
int main() {
Node* root = new Node(10);
root->left = new Node(20);
root->right = new Node(30);
root->left->left = new Node(40);
root->left->right = new Node(50);
postorderIterative(root);
return 0;
}Attempts:
2 left
💡 Hint
Two stacks reverse the order of a modified preorder traversal to get postorder.
✗ Incorrect
The first stack processes nodes root-right-left pushing to second stack, which reverses to left-right-root order, producing postorder: 40 50 20 30 10.