Binary Tree Inorder Traversal
Given the root of a binary tree, return the inorder traversal of its nodes' values. Inorder means Left, Root, Right.
Constraints:
- The number of nodes is in the range
[0, 100]. -100 <= Node.val <= 100
Intuition
Every example below uses this tree:
1 12 / \3 2 34 / \ \5 4 5 6Inorder finishes the entire left subtree before it touches the root, and only then goes right. For the tree above it gives 4, 2, 5, 1, 3, 6.
This order matters later: on a binary search tree, an inorder traversal returns the values in sorted order (on a general binary tree it does not). Many BST problems are just "do an inorder walk and look at the sequence".
Approach: Recursion
- If the current node is
null, return. - Recurse on the left child.
- Add the node's value to the answer.
- Recurse on the right child.
Same skeleton as preorder, with the add line moved between the two recursive calls.
Code
class Solution {public:void dfs(TreeNode* node, vector<int>& ans) {if (node == nullptr) return;dfs(node->left, ans);ans.push_back(node->val);dfs(node->right, ans);}vector<int> inorderTraversal(TreeNode* root) {vector<int> ans;dfs(root, ans);return ans;}};
Complexity
Time: O(n)
Each node is visited exactly once.
Space: O(h)
Recursion stack depth equals the tree height: O(log n) when balanced, O(n) when skewed.
How to Explain It in an Interview
How to Explain it in an Interview
The 30-Second Spoken Pitch
"Inorder is left, root, right. I recurse into the left subtree first, then add the current node value, then recurse into the right subtree. The base case is a null node. It is the same skeleton as preorder, only the add line moves into the middle. I would also mention that on a binary search tree inorder gives sorted order, which is why it shows up in so many BST problems. Time is O of n because each node is visited once, and space is O of h for the recursion stack."
Next TopicBinary Tree Postorder Traversal