juniorTrees

Write an algorithm to perform inorder traversal of a binary tree.

Updated Apr 28, 2026

Short answer

Inorder traversal of a binary tree visits nodes in the order: left subtree, current node, then right subtree. It can be implemented recursively using the call stack or iteratively using an explicit stack. For a binary search tree, inorder traversal produces values in sorted ascending order.

Deep explanation

Inorder traversal is a depth-first traversal technique where each node is processed after its left child subtree and before its right child subtree.

The algorithm follows these steps:

  1. Traverse the left subtree recursively.
  2. Visit the current node (for example, print or store its value).
  3. Traverse the right subtree recursively.

For a tree like:

TypeScript
4
       / \
      2   6
     / \ / \
    1  3 5  7

The inorder traversal is:

TypeScript
1 -> 2 -> 3 -> 4 -> 5 -> 6 -> 7

Recursive approach

The recursive solution is usually the simplest because the function call stack naturally keeps track of the nodes that still need to be processed.

Python
class TreeNode:
    def __init__(self, value):
        self.value = value
        self.left = None
        self.right = None




def inorder_traversal(root):
    result = []


    def traverse(node):
        if node is None:
            return


        traverse(node.left)
        result.append(node.value)
        traverse(node.right)


    traverse(root)
    return result

Complexity analysis

For a tree with n nodes:

  • Time complexity: `O(n)`
  • Every node is visited exactly once.
  • Space complexity: `O(h)`
  • h is the height of the tree.
  • The recursive call stack stores nodes along the current path.
  • In a balanced tree, this is O(log n).
  • In a completely unbalanced tree, this can become O(n).

Iterative approach

An iterative solution avoids recursion by manually maintaining a stack. It is useful when the tree may be very deep and recursion depth could become a problem.

Python
def inorder_traversal(root):
    result = []
    stack = []
    current = root


    while current or stack:
        while current:
            stack.append(current)
            current = current.left


        current = stack.pop()
        result.append(current.value)


        current = current.right


    return result

The stack represents nodes whose left subtrees have already been explored but whose values have not yet been processed. After visiting a node, the algorithm moves to its right subtree and repeats the same process.

Both approaches are valid interview solutions. The recursive version is preferred for clarity, while the iterative version demonstrates better control over memory usage and traversal state.

Real-world example

A common real-world use of inorder traversal is retrieving sorted data from a binary search tree. For example, a database index or an in-memory data structure may store records in a binary search tree, and inorder traversal can output the records in ascending order.

Python
class Product:
    def __init__(self, price):
        self.price = price
        self.left = None
        self.right = None




def get_prices_in_order(root):
    prices = []


    def inorder(node):
        if node:
            inorder(node.left)
            prices.append(node.price)
            inorder(node.right)


    inorder(root)
    return prices




# A binary search tree containing product prices
#       50
#      /  \
#    20    80
#          /
#        60


# Output: [20, 50, 60, 80]

This allows a system to display products from the lowest price to the highest price without sorting the values separately.

Common mistakes

  • * Forgetting that inorder traversal requires the order **left subtree → current node → right subtree**.
  • * Processing the current node before visiting the left subtree, which turns it into preorder traversal.
  • * Traversing only one side of the tree and missing nodes in the opposite subtree.
  • * Not handling the base case where the current node is `None`.
  • * Assuming inorder traversal always gives sorted output for any binary tree
  • it is only sorted when the tree is a binary search tree.
  • * Using recursion without considering stack depth for extremely unbalanced trees.

Follow-up questions

  • How would you modify inorder traversal to return only the kth smallest value in a binary search tree?
  • What is the difference between inorder, preorder, and postorder traversal?
  • How can you implement inorder traversal without recursion?
  • When would you prefer an iterative traversal over a recursive traversal?
  • Can inorder traversal be performed on a tree with no extra space?

More Trees interview questions

View all →