Problem Explanation

In this problem, we are given the root node of a binary tree. Our task is to perform a post-order traversal of the binary tree and return the sequence of node values.

Binary Tree is a type of tree data structure in which a node can have at most two child nodes, referred to as the left child and right child. Postorder traversal is a depth-first type of tree traversal algorithm where the algorithm first visits the left subtree, then it visits the right subtree, and lastly, it visits the root node.

As an example consider the given binary tree:

1
2
3   1
4    \
5     2
6    /
7   3

The post-order traversal of this tree would result in the sequence [3,2,1].

Approach

We can solve this problem using a recursive approach. The base case for our recursion would be when the root node is null, i.e., there are no nodes in the tree. In such cases, we don't need to do anything, so we return.

If the root node is not null, we call our recursive function on the left subtree of the root node. This will make sure that we first process all nodes in the left subtree. After this, we make a recursive call on the right subtree. Lastly, after we have visited all nodes in the left and right subtrees, we add the root node's value to our result list.

Solution

Here are the solutions in various programming languages.

Python

1
2python
3class Solution:
4    def postorderTraversal(self, root):
5        res = []
6        self.helper(root, res)
7        return res
8
9    def helper(self, root, res):
10        if root:
11            self.helper(root.left, res)
12            self.helper(root.right, res)
13            res.append(root.val)

Java

1
2java
3class Solution {
4    public List<Integer> postorderTraversal(TreeNode root) {
5        List<Integer> res = new ArrayList<>();
6        helper(root, res);
7        return res;
8    }
9
10    private void helper(TreeNode root, List<Integer> res) {
11        if (root != null) {
12            helper(root.left, res);
13            helper(root.right, res);
14            res.add(root.val);
15        }
16    }
17}

JavaScript

1
2javascript
3var postorderTraversal = function(root) {
4    let res = [];
5    helper(root, res);
6    return res;
7};
8
9var helper = function(root, res) {
10    if (root) {
11        helper(root.left, res);
12        helper(root.right, res);
13        res.push(root.val);
14    }
15};

C++

1
2cpp
3class Solution {
4public:
5    void helper(TreeNode* root, vector<int>& res) {
6        if (root) {
7            helper(root->left, res);
8            helper(root->right, res);
9            res.push_back(root->val);
10        }
11    }
12
13    vector<int> postorderTraversal(TreeNode* root) {
14        vector<int> res;
15        helper(root, res);
16        return res;
17    }
18};

C#

1
2csharp
3public class Solution {
4    List<int> res = new List<int>();
5    
6    public IList<int> PostorderTraversal(TreeNode root) {
7        if(root == null){
8            return res;
9        }
10        PostorderTraversal(root.left);
11        PostorderTraversal(root.right);
12        res.Add(root.val);
13        return res;
14    }
15}

In all the above solutions, helper is a recursive function that performs the post-order traversal. It first processes the left subtree, then the right subtree, and lastly, it processes the root node. This traversal is ensured by the sequence of the recursive function calls. The sequence of node values is stored in a list/array which is returned as the result.# Time Complexity

The time complexity of the post-order traversal algorithm is O(n), where n is the number of nodes in the binary tree. This is because we visit each node once.

Space Complexity

The space complexity of the post-order traversal algorithm is also O(n), where n is the number of nodes in the binary tree. This is due to the maximum amount of space required by the recursion stack in the worst-case scenario, which occurs when the binary tree is skewed, i.e., each node has only one child node. The depth of the recursion tree equals the number of nodes in the binary tree, hence the space complexity is O(n).

Conclusion

Post-order traversal of a binary tree is a fundamental operation for many tasks in computer science, such as expression tree evaluation and solving certain dynamic programming problems. The recursive approach provided in this article is straightforward, efficient and easy to understand. However, the same task can be accomplished using an iterative approach with the help of a stack, but it can be a bit more complex than the recursive one. All solutions provided follow the same algorithmic concept with slightly different implementations based on the syntax of the respective programming languages.