Coding interview problems › Trees & BSTs

🌳 Trees & BSTs Easy

Binary Tree Inorder, Preorder & Postorder Traversal

Binary tree inorder, preorder and postorder traversal explained: recursive and iterative Python, when each order is used, common mistakes and a live visual.

Also searched as: tree traversal inorder preorder postorder · iterative inorder traversal with a stack · DFS traversals of a binary tree

🌳

Try it live Free

Binary Search Tree & Traversals

Build a tree in the BST lab, then run in-order, pre-order, post-order and level-order and watch the output list fill as the walk visits each node.

Also useful: Recursion & the Call Stack

Open the playground →

The problem

Given the root of a binary tree, return the values of its nodes in inorder (left, node, right), preorder (node, left, right) and postorder (left, right, node) order.

Inputroot = [1, null, 2, 3] (1 has right child 2; 2 has left child 3)
Outputinorder [1, 3, 2], preorder [1, 2, 3], postorder [3, 2, 1]

The key insight

All three traversals are the same depth-first walk; they only differ in when you write down the current node: before its children (pre), between them (in), or after both (post). Recursion uses the call stack for you; the iterative version makes that stack explicit. For a binary search tree, inorder visits values in sorted order.

Brute force first: There is no slower brute force here; the real choice is recursion (clean, but deep trees can hit Python's recursion limit) versus an explicit stack.

Step-by-step approach

  1. Write a recursive helper dfs(node) that returns immediately on None.
  2. Preorder: record node.val, then recurse left, then right.
  3. Inorder: recurse left, record node.val, recurse right.
  4. Postorder: recurse left, recurse right, then record node.val.
  5. Iterative inorder: push nodes while walking left; when you cannot go left, pop, record it, and move to its right child.

Python solution

PYTHON 3tested
class TreeNode:
    def __init__(self, val=0, left=None, right=None):
        self.val, self.left, self.right = val, left, right


def preorder(root):
    out = []
    def dfs(node):
        if node:
            out.append(node.val)
            dfs(node.left)
            dfs(node.right)
    dfs(root)
    return out


def inorder(root):
    out, stack, node = [], [], root   # iterative version
    while stack or node:
        while node:                    # go as far left as possible
            stack.append(node)
            node = node.left
        node = stack.pop()
        out.append(node.val)
        node = node.right
    return out


def postorder(root):
    out = []
    def dfs(node):
        if node:
            dfs(node.left)
            dfs(node.right)
            out.append(node.val)
    dfs(root)
    return out

Complexity

TimeO(n)
SpaceO(h)

Each node is visited exactly once. The stack (call stack or explicit) holds at most one root-to-leaf path, so extra space is the height h: O(log n) for a balanced tree, O(n) for a skewed one.

Common mistakes

Frequently asked questions

What is the time and space complexity of tree traversals?

O(n) time because every node is visited once, and O(h) extra space for the stack, where h is the tree height. That is O(log n) for a balanced tree and O(n) for a skewed one.

Which traversal gives sorted output for a BST?

Inorder. In a binary search tree every left subtree is smaller and every right subtree larger, so left, node, right visits values in ascending order.

When would I use preorder or postorder?

Preorder is natural for copying or serialising a tree because a parent comes before its children. Postorder suits problems where a node needs its children's answers first, such as height, deleting a tree or evaluating an expression tree.

Can I traverse without recursion or a stack?

Yes, Morris traversal temporarily rewires right pointers to walk the tree in O(1) extra space and restores them afterwards. It is a good follow-up answer but rarely required.

Preparing for placements?

Take the 2-minute readiness check to find your weak patterns, then follow the placement path from DSA core to system design.

📋 2-minute readiness check The full placement path

All coding interview problems More Trees & BSTs Binary Search Tree & Traversals lab Placement prep guides

Problem statements on this site are written in our own words. Problem names are the common names used across interview-prep communities; BitBootcamp is an independent learning platform and is not affiliated with LeetCode or any company that asks these questions.