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

Challenge - 5 Problems

❓ Predict Output

intermediate

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;
}

A 1 2 3 4 5

B 4 5 2 3 1

C 2 4 5 3 1

D 4 2 5 3 1

💡 Hint

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

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

intermediate

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?

A 8

B 6

C 7

D Depends on the tree structure

💡 Hint

Postorder traversal visits every node exactly once.

Postorder traversal visits all nodes in the tree exactly once, so the count equals the total number of nodes.

🔧 Debug

advanced

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;
}

A Compilation error

B 20 30 10

C No output

D 30 20 10

💡 Hint

Check the order of recursive calls for left and right children.

The code visits right subtree first, then left subtree, then root, so output is 30 20 10 instead of standard postorder.

🚀 Application

advanced

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;
}

A 7 6 8 5

B 6 7 8 5

C 5 8 6 7

D 7 8 6 5

💡 Hint

Follow left, then right, then root order carefully for each subtree.

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

expert

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;
}

A 40 50 20 30 10

B 10 20 30 40 50

C 50 40 20 30 10

D 20 40 50 30 10

💡 Hint

Two stacks reverse the order of a modified preorder traversal to get postorder.

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.