145. Binary Tree Postorder Traversal

 

Binary Tree Postorder Traversal

Problem Description

Given the root of a binary tree, return the postorder traversal of its nodes' values. 

Example 1:

Input: root = [1,null,2,3]
Output: [3,2,1]

Example 2:

Input: root = []
Output: []

Example 3:

Input: root = [1]
Output: [1]

 

Constraints:

• The number of the nodes in the tree is in the range [0, 100].
• -100 <= Node.val <= 100

 

Follow up: Recursive solution is trivial, could you do it iteratively?

(Image from: https://github.com/MisterBooo/LeetCodeAnimation )

Approach) Use two stacks

• Push the root to the first stack.
• Loop while the first stack is not empty
• Pop a node from the first stack and push it to the second stack(res[])
• Push left and right children of the popped node to the first stack
• Pop all elements from second stack(res.reverse())

Code:

/**
 * Definition for a binary tree node.
 * function TreeNode(val, left, right) {
 *     this.val = (val===undefined ? 0 : val)
 *     this.left = (left===undefined ? null : left)
 *     this.right = (right===undefined ? null : right)
 * }
 */
/**
 * @param {TreeNode} root
 * @return {number[]}
 */
var postorderTraversal = function(root) {
    let res = []; // use res as another stack
    // empty tree case:
    if (root === null) return res;
    let stack = [];
    
    // postorder visit: left, right, root
    stack.push(root);
    while (stack.length !== 0) { 
        let cur = stack.pop();
        // treat it as stack, store them in reverse order:
        // i.e root, left, right
        res.push(cur.val); 
        if (cur.left) stack.push(cur.left);
        if (cur.right) stack.push(cur.right);
    }
    
    // we can pop all elements one by one, or just reverse them
    return res.reverse();
};

Approach) Recursion

/**
 * Definition for a binary tree node.
 * function TreeNode(val, left, right) {
 *     this.val = (val===undefined ? 0 : val)
 *     this.left = (left===undefined ? null : left)
 *     this.right = (right===undefined ? null : right)
 * }
 */
/**
 * @param {TreeNode} root
 * @return {number[]}
 */
var postorderTraversal = function (root) {
    const ans = [];
    postorder(root);
    return ans;

    function postorder(root) {
        if (root === null) {
            return;
        }
        postorder(root.left);
        postorder(root.right);
        ans.push(root.val);
    }
}

Complexity 

Time Complexity
Time complexity will be O(n).

Space Complexity
space complexity should also be O(n).

Approach) Iterative — Using 1 stack

/**
 * Definition for a binary tree node.
 * function TreeNode(val, left, right) {
 *     this.val = (val===undefined ? 0 : val)
 *     this.left = (left===undefined ? null : left)
 *     this.right = (right===undefined ? null : right)
 * }
 */
/**
 * @param {TreeNode} root
 * @return {number[]}
 */
var postorderTraversal = function (root) {
    const ans = [];
    const stack = [];
    let node = root;
    let times = 1;
    while (node !== null || stack.length !== 0) {
        while (node !== null) {
            stack.push([node, 1]);
            node = node.left;
        }
        [node, times] = stack.pop();
        if (times === 2) {
            ans.push(node.val);
            node = null;
        } else {
            stack.push([node, 2]);
            node = node.right;
        }
    }
    return ans;
};

Complexity 

Time Complexity
Time complexity will be O(n).

Space Complexity
space complexity should also be O(n).

Conclusion

That’s all folks! In this post, we solved LeetCode problem #145. Binary Tree Postorder Traversal

I hope you have enjoyed this post. Feel free to share your thoughts on this.

You can find the complete source code on my GitHub repository. If you like what you learn. feel free to fork 🔪 and star ⭐ it.

In this blog, I have tried to collect & present the most important points to consider when improving Data structure and logic, feel free to add, edit, comment, or ask. For more information please reach me here
Happy coding!