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

Binary Tree Inorder Traversal – Solution & Complexity

Interview solutions
/
Binary Tree Inorder Traversal

Solution Walkthrough

  1. Step 1: Recognize the traversal order

    In-order traversal always follows the same pattern at every node: visit the left subtree, then record the current node, then visit the right subtree. That makes this a straightforward depth-first search problem.

  2. Step 2: Recursive DFS solution

    Use a helper DFS that stops on None, recursively processes the left child, appends the current value, and then processes the right child. This mirrors the definition of in-order traversal directly.

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

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

    dfs(root)
    return result

  3. Step 3: Think through edge cases

    An empty tree should return []. A single node should return just that value. Skewed trees should still work because the traversal naturally unwinds back up the call stack in the correct left-node-right order.

  4. Step 4: Iterative stack solution and complexity

    Time: O(n) because each node is pushed and popped at most once. Space: O(h) for the stack, where h is the tree height (O(n) worst case on a skewed tree). The iterative version simulates the recursive call stack explicitly: keep walking left, pop the next node to visit, record it, then move to its right subtree.

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

    while stack or node is not None:
        while node is not None:
            stack.append(node)
            node = node.left

        node = stack.pop()
        result.append(node.val)
        node = node.right

    return result

FAQ

See also

Practice Binary Tree Inorder Traversal online (run code in the browser)Binary Tree Postorder 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?