Problem overview
The method inorderTraversal receives the root of a binary tree, a TreeNode | null, and returns the node values as a number[] in inorder: the whole left subtree first, then the node itself, then the whole right subtree. The rule applies at every node, not just at the root.
In the example, node 1 has no left child and a right child 2, and node 2 has a left child 3. Visiting 1 means: nothing on its left, then 1, then its right subtree. That subtree is visited as 3 (the left child of 2), then 2. The result is [1, 3, 2].
The statement also asks whether you can do it iteratively. This lesson uses recursion, which maps directly onto the definition; an iterative version is sketched at the end.
Approach: let the definition be the code
The definition is already recursive: "inorder of a tree" is "inorder of the left subtree, the root, inorder of the right subtree". An empty subtree contributes nothing, and that is the base case that stops the recursion.
Instead of building and concatenating a new array at every call, the lesson passes one shared array down the recursion. Each call appends to it. The order of the three lines inside the helper is the whole algorithm: move the push before the left call and you get preorder, move it after the right call and you get postorder.
Step by step
- Declare the helper
dfsaboveinorderTraversal. It takes the subtree root, typedTreeNode | nullbecause a child may be missing, and the array to fill. It returnsvoid, since its work shows up in the array. - Handle the empty subtree. If
rootis falsy, return. After that check TypeScript knowsrootis aTreeNode, soroot.leftandroot.valare allowed below it. - Recurse left. Everything in the left subtree must come before the current node.
- Push the node's value. By now the whole left subtree is already in the array.
- Recurse right. The right subtree goes after the node.
- Create the result array in
inorderTraversal: an emptynumber[]declared withconst. - Call the helper with the root and the array.
- Return the array.
The solution in TypeScript
class Solution {
dfs(root: TreeNode | null, result: number[]): void {
if (!root) {
return;
}
this.dfs(root.left, result);
result.push(root.val);
this.dfs(root.right, result);
}
inorderTraversal(root: TreeNode | null): number[] {
const result: number[] = [];
this.dfs(root, result);
return result;
}
}
TypeScript details worth knowing:
- Methods call each other through
this. Writingdfs(root.left, result)alone would look for a variable nameddfs, not the method, and the compiler would report it as unknown. constprotects the variable, not the array.resultcan't be reassigned, butpushstill changes the array it points to. Arrays are objects, so the helper and the caller share the same array. That sharing is why the helper doesn't need to return anything.- Narrowing with
!root. The typeTreeNode | nullsays the value may benull. After the early return, the compiler narrows the type toTreeNodefor the rest of the method. The annotations only matter to the compiler; they are erased when the code is compiled to JavaScript.
Complexity
Time: O(n). Each node is visited once, and each visit does a constant amount of work: one comparison and one push. The calls on missing children return immediately, and there are at most n + 1 of them.
Space: O(h) for the call stack, where h is the height of the tree, plus the O(n) output array. A balanced tree has h around log n. A tree where every node has only a left child has h = n, and a recursion that deep can overflow the stack: in Node a chain of 20,000 left children is enough to throw a RangeError with the default stack size.
The iterative follow-up
The follow-up replaces the call stack with an explicit one. Walk left as far as possible, pushing every node on a stack. Then pop a node, record it, and move to its right child, and repeat.
function inorderIterative(root: TreeNode | null): number[] {
const result: number[] = [];
const stack: TreeNode[] = [];
let current = root;
while (current || stack.length > 0) {
while (current) {
stack.push(current);
current = current.left;
}
const node = stack.pop()!;
result.push(node.val);
current = node.right;
}
return result;
}
It returns the same [1, 3, 2] for the example. The explicit stack lives on the heap, so the 20,000-node left chain works too. The trailing ! after pop() tells the compiler the result is not undefined; it is safe here because the loop only reaches that line with a non-empty stack.
Edge cases and common mistakes
- An empty tree.
rootisnull, the helper returns at once, and the result is[]. - A single node. Both recursive calls hit the base case, and the result is just that node's value.
- Wrong order. Pushing before the left call gives preorder: for the example,
[1, 2, 3]. Pushing after the right call gives postorder:[3, 2, 1]. - Forgetting to pass
resultalong. Each call would need its own array, and the values from deeper calls would be lost. - Returning a value from
dfsand ignoring it. The helper's return type isvoid; the data travels through the shared array. - Skipping the null check.
root.leftonnullthrows aTypeErrorat run time.
Testing
- The example tree gives
[1, 3, 2]. - An empty tree gives
[]. - A tree with root 2, left child 1 and right child 3 gives
[1, 2, 3]: for a search tree, inorder is sorted order.