Inorder Traversal of Binary Tree
EasyLeft, then root, then right
Problem
Return the inorder traversal (left, root, right) of a binary tree.
Recurse left, visit the node, then recurse right (Left-Node-Right) — sorted order for a BST.
The idea
Fully traverse the left subtree before visiting the node, then the right. On a binary search tree this emits the values in sorted order, which is the single most exploited fact about BSTs.
The trick
- Sorted output on a BST — the basis of kth-smallest, validation and recovery.
- The node is visited between its two subtrees, never before.
Step 1 of 8. Inorder = Left → Node → Right. We dive left first, emit the node, then go right.
1/8
Optimal
timeO(n)spaceO(h)
Order = when you emit the node.
1function inorder(node) {2 if (!node) return;3 inorder(node.left);4 visit(node.val); // node between children5 inorder(node.right);6}Input
- nodes
- 6, 5 edges
Output
- output
- —
- inorder
- —
Check yourself
3 quick questions about this walkthrough. A wrong answer costs nothing.
Examples
Example 1
- Input:
- tree = [1,null,2,3]
- Output:
- [1, 3, 2]
- Explanation:
- Left, node, right → 1,3,2.
Example 2
- Input:
- tree = [1,2,3]
- Output:
- [2, 1, 3]
- Explanation:
- Gives 2,1,3.
Example 3
- Input:
- tree = []
- Output:
- []
- Explanation:
- Empty → nothing.
Practice this problem:LeetCode(opens in a new tab)Search GeeksforGeeks(opens in a new tab)
Finished the walkthrough? Add it to your streak.