{ }DevToolsDaily
ToolsInterview Prep
New
CheatsheetsDirectoryMy spaceBlog
Ctrl + K
Ask AI

Binary Tree Postorder Traversal – Solution & Complexity

Interview solutions
/
Binary Tree Postorder Traversal

Solution Walkthrough

  1. Step 1: Recursive depth-first traversal

    Postorder traversal is defined recursively: traverse the left subtree, then the right subtree, then record the current node. A helper DFS mirrors that definition directly and is the easiest way to get started.

    def postorder_traversal(root: TreeNode) -> list[int]:
    result = []

    def dfs(node):
        if node is None:
            return
        dfs(node.left)
        dfs(node.right)
        result.append(node.val)

    dfs(root)
    return result

  2. Step 2: Single-stack iterative solution

    To avoid recursion, simulate the call stack yourself. Walk left as far as possible, peek at the top node, and only visit it after its right subtree is done. Tracking the last visited node lets one stack handle the full postorder order, which is more efficient than using a second stack but also a bit trickier to reason about.

    def postorder_traversal(root: TreeNode) -> list[int]:
    result = []
    stack = []
    node = root
    last_visited = None

    while stack or node is not None:
        if node is not None:
            stack.append(node)
            node = node.left
        else:
            peek = stack[-1]
            if peek.right is not None and last_visited is not peek.right:
                node = peek.right
            else:
                result.append(peek.val)
                last_visited = stack.pop()

    return result

FAQ

See also

Practice Binary Tree Postorder Traversal online (run code in the browser)Binary Tree Inorder Traversal solution (easy)Binary Tree Preorder Traversal solution (easy)Balanced Binary Tree solution (easy)Diameter of Binary Tree solution (easy)All coding interview problems
Buy me a coffeePrivacyTermsFAQChangelogFeature RequestsBlogAll ToolsPricingContact Us © Monkey SkatesHave kids?