145. Binary Tree Postorder Traversal

Description

The problem is to perform a postorder traversal on a binary tree. In a postorder traversal, the nodes are visited in the following order: left subtree, right subtree, and then the root node. The task is to return a list of node values in the order they are visited during the traversal.

Intuition

Postorder traversal can be seen as a bottom-up approach to tree traversal. It is intuitive because it processes all child nodes before processing the parent node, which is often useful in scenarios where a node's state depends on the states of its children. The recursive nature of trees makes recursion a natural fit for this traversal.

Approach

1. Recursive Function: - Create a helper function traverse that takes the current node and a list result as arguments. - If the current node is null, return immediately. - Recursively call the traverse function on the left child, followed by the right child. - After both children have been processed, add the current node's value to the result list.
2. Initialization: - Start by initializing an empty list result that will store the node values in postorder. - Call the traverse function with the root of the tree and the list result. - Finally, return the list result which contains the postorder traversal of the tree.

Complexity

Time Complexity:

(O(N)), where (N) is the number of nodes in the tree. Each node is visited exactly once during the traversal.

Space Complexity:

• Recursive Call Stack: (O(H)), where (H) is the height of the tree. In the worst case, the height could be (O(N)) for a skewed tree.
• Auxiliary Space:(O(N)) for storing the result list result, which contains the node values.

Code

C++

class Solution {
public:
    void traverse(TreeNode* node, std::vector& result) {
        if (node == nullptr)
            return;

        traverse(node->left, result);
        traverse(node->right, result);
        result.push_back(node->val);
    }

    std::vector postorderTraversal(TreeNode* root) {
        std::vector result;
        traverse(root, result);
        return result;
    }
};

Python

class TreeNode:
    def __init__(self, x):
        self.val = x
        self.left = None
        self.right = None

class Solution:
    def traverse(self, node, result):
        if not node:
            return

        self.traverse(node.left, result)
        self.traverse(node.right, result)
        result.append(node.val)

    def postorderTraversal(self, root):
        result = []
        self.traverse(root, result)
        return result

Java

class Solution {
    private void traverse(TreeNode node, List result) {
        if (node == null)
            return;

        traverse(node.left, result);
        traverse(node.right, result);
        result.add(node.val);
    }

    public List postorderTraversal(TreeNode root) {
        List result = new ArrayList<>();
        traverse(root, result);
        return result;
    }
}

JavaScript

var postorderTraversal = function(root) {
    
    let result = [];
    
    function traverse(node)
    {
        if(node === null)
            return 0;
        
        traverse(node.left);
        traverse(node.right);
        result.push(node.val);
    }
    
    traverse(root);
    return result;
};