LeetCode #94 Easy

Binary Tree Inorder Traversal

Given the root of a binary tree, return the inorder traversal of its node values: left subtree, then the node, then the right subtree.

binary treedfsrecursion

Open on LeetCode ↗

02

Intuition

💡

Inorder is just three lines that call themselves: finish everything on the left, record the node, then do the right. The call stack remembers where you came from — on a BST this visits values in sorted order.

03

Approach

1

Trust the recursive definition

Inorder of a tree = inorder of the left subtree + this node + inorder of the right subtree. That sentence is the algorithm — write a helper that recurses left, appends node.val, then recurses right. An empty child is the base case: return without doing anything.

2

The call stack does the bookkeeping

No manual tracking is needed: when the left recursion returns, execution resumes exactly at the append. That's why the traversal 'climbs back up' for free. Depth of recursion equals the height of the tree.

3

Iterative version, if asked

Interviewers often follow up with 'now without recursion'. Simulate the stack yourself: push nodes while running left, pop to visit, then switch to the popped node's right child. Same order, explicit stack.

04

Solution & live demo

python

▶1class Solution:
▶2    def inorderTraversal(self, root):
▶3        res = []
▶4        def dfs(node):
▶5            if not node:
▶6                return
▶7            dfs(node.left)
▶8            res.append(node.val)
▶9            dfs(node.right)
▶10        dfs(root)
▶11        return res

05

Edge cases

Empty tree

The base case fires immediately — return the empty list.

Skewed tree (all left or all right children)

Recursion depth reaches n, so the traversal degenerates to a simple walk; output is still correct.

Single node

Left recursion returns instantly, node is visited, right returns — result is [root.val].

06

Complexity

Time

O(n)

Space

O(h)

Every node visited once; the recursion stack holds one path — h is the tree height.