Binary Tree Inorder Traversal
Easy · Trees · Stack · Tree · Depth-First Search · Binary Tree
Problem
Given the root of a binary tree, return the inorder traversal of its values: the entire left subtree, then the node itself, then the entire right subtree.
For a binary search tree this yields the values in sorted order. Try writing it iteratively as well as recursively.
Examples
Input: root = [6,2,8,1,4] Output: [1,2,4,6,8]
This tree is a binary search tree, so inorder gives the values sorted.
Input: root = [3,None,5,7] Output: [3,7,5]
3 has no left child; then comes the right subtree, where 7 is the left child of 5.
Input: root = [1] Output: [1]
A single node.
Constraints
- The tree has between 0 and 100 nodes
- -100 <= Node.val <= 100
Approaches
- Baseline: recursion — time O(n), space O(h) call stack
Follow-up
All three depth-first orders differ only in when the node is visited. The use cases ask for preorder (node first) and postorder (node last), whose iterative forms differ from inorder's in instructive ways. Morris traversal does any of them in O(1) extra space by threading the tree temporarily.
Related problems
Start free on Cariara · Coding problems · System design studio
