Post Order Tree Traversal II in C++ (Time Complexity: O(n))

Input: [1,null,2,3]
   1
    \
     2
    /
   3

Output: [3,2,1]

Understanding the Problem

The core challenge of this problem is to perform a postorder traversal of a binary tree. In postorder traversal, we visit the left subtree, then the right subtree, and finally the root node. This traversal is significant in various applications such as expression tree evaluations and syntax tree traversals.

Potential pitfalls include misunderstanding the traversal order and handling null nodes incorrectly.

Approach

To solve this problem, we can consider both recursive and iterative approaches:

Naive Solution: Recursive Approach

The recursive approach is straightforward but not optimal for large trees due to potential stack overflow issues. Here is a simple recursive solution:

// Recursive Postorder Traversal
void postorderTraversal(TreeNode* root, vector<int>& result) {
    if (root == nullptr) return;
    postorderTraversal(root->left, result);
    postorderTraversal(root->right, result);
    result.push_back(root->val);
}

While this solution is easy to implement, it is not suitable for the follow-up requirement of an iterative solution.

Optimized Solution: Iterative Approach

To achieve an iterative solution, we can use two stacks. The first stack is used to traverse the tree, and the second stack is used to store the nodes in postorder. Here is the detailed algorithm:

1. Initialize two stacks: stack1 and stack2.
2. Push the root node to stack1.
3. While stack1 is not empty:
   • Pop a node from stack1 and push it to stack2.
   • Push the left and right children of the popped node to stack1.
4. Pop all nodes from stack2 and add their values to the result list.

Algorithm

Here is a step-by-step breakdown of the iterative algorithm:

// Iterative Postorder Traversal
vector<int> postorderTraversal(TreeNode* root) {
    vector<int> result;
    if (root == nullptr) return result;

    stack<TreeNode*> stack1, stack2;
    stack1.push(root);

    while (!stack1.empty()) {
        TreeNode* node = stack1.top();
        stack1.pop();
        stack2.push(node);

        if (node->left) stack1.push(node->left);
        if (node->right) stack1.push(node->right);
    }

    while (!stack2.empty()) {
        result.push_back(stack2.top()->val);
        stack2.pop();
    }

    return result;
}

Code Implementation

Below is the complete C++ code for the iterative postorder traversal:

#include <iostream>
#include <vector>
#include <stack>
using namespace std;

// Definition for a binary tree node.
struct TreeNode {
    int val;
    TreeNode* left;
    TreeNode* right;
    TreeNode(int x) : val(x), left(nullptr), right(nullptr) {}
};

vector<int> postorderTraversal(TreeNode* root) {
    vector<int> result;
    if (root == nullptr) return result;

    stack<TreeNode*> stack1, stack2;
    stack1.push(root);

    while (!stack1.empty()) {
        TreeNode* node = stack1.top();
        stack1.pop();
        stack2.push(node);

        if (node->left) stack1.push(node->left);
        if (node->right) stack1.push(node->right);
    }

    while (!stack2.empty()) {
        result.push_back(stack2.top()->val);
        stack2.pop();
    }

    return result;
}

// Helper function to create a new tree node
TreeNode* newNode(int data) {
    TreeNode* node = new TreeNode(data);
    node->left = node->right = nullptr;
    return node;
}

// Main function to test the postorder traversal
int main() {
    TreeNode* root = newNode(1);
    root->right = newNode(2);
    root->right->left = newNode(3);

    vector<int> result = postorderTraversal(root);
    for (int val : result) {
        cout << val << " ";
    }
    return 0;
}

Complexity Analysis

The time complexity of the iterative approach is O(n), where n is the number of nodes in the tree. This is because each node is processed exactly twice. The space complexity is also O(n) due to the use of two stacks.

Edge Cases

Consider the following edge cases:

• An empty tree (root is null).
• A tree with only one node.
• A tree where all nodes are on one side (e.g., a linked list).

Each of these cases should be handled correctly by the algorithm.

Testing

To test the solution comprehensively, consider the following test cases:

• Simple tree with a few nodes.
• Tree with only left children.
• Tree with only right children.
• Balanced tree.
• Unbalanced tree.

Use a variety of test cases to ensure the algorithm works correctly in all scenarios.

Thinking and Problem-Solving Tips

When approaching such problems, consider the following tips:

• Understand the traversal order and its significance.
• Break down the problem into smaller steps.
• Consider both recursive and iterative solutions.
• Practice solving similar problems to improve your skills.

Conclusion

In this blog post, we discussed the problem of postorder tree traversal and provided both recursive and iterative solutions. We analyzed the complexity and discussed edge cases and testing strategies. Understanding and solving such problems is crucial for improving problem-solving skills and preparing for technical interviews.

Additional Resources

For further reading and practice, consider the following resources:

• LeetCode: Binary Tree Postorder Traversal
• GeeksforGeeks: Tree Traversals
• Coursera: Data Structures