algoadvance

Leetcode 145. Binary Tree Postorder Traversal

Problem Statement

Given the root of a binary tree, return the postorder traversal of its nodes’ values. Postorder traversal is a type of depth-first traversal where the nodes are recursively visited in this order: left subtree, right subtree, root.

For example, given a binary tree:

    1
     \
      2
     /
    3

You should return the list [3, 2, 1].

Clarifying Questions

1. Input Constraints:
   • Can the binary tree be empty (i.e., root is nullptr)?
     • Yes, the function should return an empty list in this case.
   • What is the maximum number of nodes in the tree?
     • The number of nodes can be up to (10^4).
2. Node Values:
   • Are the node values unique?
     • Yes, for simplification we can assume node values are unique.
   • Could the node values be negative?
     • Yes, node values can be negative.

Strategy

To solve this, we can use a recursive approach to traverse the tree in postorder. A postorder traversal visits nodes in the order:

1. Visit left subtree.
2. Visit right subtree.
3. Visit root.

For each node, we will:

1. Recursively visit its left child.
2. Recursively visit its right child.
3. Process the root node (i.e., add its value to the result list).

Code

Here’s how you can implement the postorder traversal recursively in C++:

#include <vector>

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

class Solution {
public:
    std::vector<int> postorderTraversal(TreeNode* root) {
        std::vector<int> result;
        postorderHelper(root, result);
        return result;
    }

private:
    void postorderHelper(TreeNode* node, std::vector<int>& result) {
        // Base case: if the node is null, just return.
        if (node == nullptr) return;

        // Recursive case: visit left subtree first.
        postorderHelper(node->left, result);

        // Then visit right subtree.
        postorderHelper(node->right, result);

        // Visit the node itself.
        result.push_back(node->val);
    }
};

Time Complexity

• Time Complexity: (O(n)), where (n) is the number of nodes in the tree. Each node is visited exactly once.
• Space Complexity: (O(n)). In the worst case, the recursion stack can go as deep as the height of the tree, which can be (O(n)) in the case of a skewed tree (or (O(\log n)) in the best case of a balanced tree). Additionally, we use (O(n)) space to store the result.

This should cover all necessary aspects to solve the problem using a recursive approach. If you have further questions or need an iterative solution, feel free to ask!

Cut your prep time in half and DOMINATE your interview with AlgoAdvance AI

• Got blindsided by a question you didn’t expect?

• Spend too much time studying?

• Or simply don’t have the time to go over all 3000 questions?