On this page

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 1
2 / \
3 2 3
4 / \ \
5 4 5 6

Inorder 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

  1. If the current node is null, return.
  2. Recurse on the left child.
  3. Add the node's value to the answer.
  4. 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