15 Jun 2024•C++ / Python / TypeScript•Easy

Binary Tree Postorder Traversal

Collected C++, Python, TypeScript solutions for binary tree postorder traversal. Add a dedicated write-up later if you want deeper notes.

View original LeetCode question

auto-generated entry for Binary Tree Postorder Traversal. the solution files are available below.

solution files

C++ binary-tree-postorder-traversal/synced-solution.cpp
Python binary-tree-postorder-traversal/synced-solution.py
TypeScript binary-tree-postorder-traversal/synced-solution.ts

Solution files

Python•binary-tree-postorder-traversal/synced-solution.py

class Solution:
    def postorderTraversal(self, root: Optional[TreeNode]) -> List[int]:
        result = []
        stack = []
        current = root
        last_visited = None
        while stack or current:
            if current:
                stack.append(current)
                current = current.left
            else:
                peek = stack[-class="syntax-number">1]
                if peek.right and peek.right != last_visited:
                    current = peek.right
                else:
                    result.append(peek.val)
                    last_visited = stack.pop()
        return result

C++•binary-tree-postorder-traversal/synced-solution.cpp

class Solution {
public:
    vector<int> postorderTraversal(TreeNode* root) {
        vector<int> result;
        if (!root) return result;
        stack<TreeNode*> st;
        TreeNode* current = root;
        TreeNode* last_visited = nullptr;
        while (!st.empty() || current) {
            if (current) {
                st.push(current);
                current = current->left;
            } else {
                TreeNode* peek = st.top();
                if (peek->right && peek->right != last_visited) {
                    current = peek->right;
                } else {
                    result.push_back(peek->val);
                    last_visited = peek;
                    st.pop();
                }
            }
        }
        return result;
    }
};

TypeScript•binary-tree-postorder-traversal/synced-solution.ts

function postorderTraversal(root: TreeNode | null): number[] {
    const result: number[] = [];
    const stack: TreeNode[] = [];
    let current = root;
    let last_visited: TreeNode | null = null;
    while (stack.length > class="syntax-number">0 || current) {
        if (current) {
            stack.push(current);
            current = current.left;
        } else {
            const peek = stack[stack.length - class="syntax-number">1];
            if (peek.right && peek.right !== last_visited) {
                current = peek.right;
            } else {
                result.push(peek.val);
                last_visited = stack.pop()!;
            }
        }
    }
    return result;
}