Binary Tree Inorder Traversal
The key idea
Inorder means left, node, right: for every node, fully traverse its left subtree before recording the node's own value, then traverse its right subtree. Applying that rule recursively at every node lays the values out in the inorder sequence — and for a binary search tree that sequence is sorted.
Problem
Given the root of a binary tree, return the inorder traversal of its nodes' values.
Inorder traversal visits the left subtree, then the current node, then the right subtree. For each node, you record its value only after every node in its left subtree has been visited.
Follow-up: The recursive solution is trivial. Could you do it iteratively instead?
Constraints
- The number of nodes in the tree is in the range
[0, 100]. -100 <= Node.val <= 100
Examples
Input: root = [1,null,2,3]
Output: [1,3,2]
Input: root = []
Output: []
Input: root = [1]
Output: [1]
Complexity
Time: O(n) Space: O(n)
See the full solution
- ✓Full worked approach
- ✓Reference code in 5 languages
- ✓Problem-solving tips
- ✓Step-by-step animated visualization
More Tree / Recursion problems
- Balanced Binary TreeEASY
- Binary Tree CamerasHARD
- Binary Tree Maximum Path SumHARD
- Binary Tree PathsEASY
- Binary Tree Postorder TraversalEASY
- Binary Tree Preorder TraversalEASY
- House Robber IIIMEDIUM
- Construct Binary Tree from Inorder and Postorder TraversalMEDIUM
- Construct Binary Tree from Preorder and Inorder TraversalMEDIUM
- Convert BST to Greater TreeMEDIUM
- Count Complete Tree NodesEASY
- Count Good Nodes in Binary TreeMEDIUM