Problem overview
The method inorderTraversal receives the root of a binary tree and returns the node values as an Array[Int] in inorder: the whole left subtree first, then the node itself, then the whole right subtree. The rule applies at every node, not only at the root.
In the example, 1 has no left child and a right child 2, and 2 has a left child 3. Starting at 1, the left subtree is empty, so 1 comes first. The right subtree has root 2, whose left subtree is just 3, so the order continues with 3, then 2. The result is [1, 3, 2].
The statement adds a follow-up: the recursive solution is easy, so try an iterative one. This lesson writes the recursive version.
Approach: let recursion follow the tree's shape
A tree is a node with two smaller trees below it, and an empty tree is represented by null. That makes the traversal naturally recursive. To list a tree inorder:
- If the tree is empty, add nothing.
- List the left subtree.
- Add this node's value.
- List the right subtree.
Only the position of step 3 distinguishes the three classic depth-first orders. Adding the value before both recursive calls gives preorder, and adding it after both gives postorder. Putting it between them gives inorder. For a binary search tree, inorder visits the values in ascending order, which is the main reason the order is worth knowing.
The helper does not return a list for each subtree. Instead, one shared buffer is passed down every call, and each call appends to it. That avoids building and joining many small lists.
Step by step
- Declare the helper
dfsaboveinorderTraversal. It takes the subtree'srootand the shared bufferresult, and returnsUnitbecause its work shows up in the buffer. The type is written with the full pathscala.collection.mutable.ArrayBuffer[Int], so no import is needed. - Stop at an empty subtree. If
rootisnull,returnimmediately. This is the base case that ends every branch of the recursion. - Visit the left subtree by calling
dfs(root.left, result). Everything in it is appended before the current node. - Append the node's value with
result += root.value. The lesson'sTreeNodekeeps its number in the fieldvalue. - Visit the right subtree with
dfs(root.right, result). - In
inorderTraversal, createresultas an emptyArrayBuffer[Int]withval. - Call
dfs(root, result)to fill the buffer. - Return
result.toArrayto turn the buffer into theArray[Int]the method promises.
The solution in Scala
class Solution {
def dfs(root: TreeNode, result: scala.collection.mutable.ArrayBuffer[Int]): Unit = {
if (root == null) {
return
}
dfs(root.left, result)
result += root.value
dfs(root.right, result)
}
def inorderTraversal(root: TreeNode): Array[Int] = {
val result = scala.collection.mutable.ArrayBuffer[Int]()
dfs(root, result)
result.toArray
}
}
The Scala details worth a closer look:
- Buffers grow, arrays don't. A Scala
Arrayhas a fixed size, so the traversal collects values in a growableArrayBufferand converts it once at the end withtoArray. valfixes the name, not the contents.resultis aval, butresult += root.valuestill changes the buffer, because+=on a mutable buffer appends in place.- The buffer is shared.
dfsreceives a reference to the same buffer in every call, so values appended by deep calls are visible to the caller once they return. - The final expression is the result. In
inorderTraversal,result.toArrayis the last line, so noreturnis needed. Indfs,returnis only there for the early exit. Writingif (root != null) { ... }around the three lines would avoid it. nullmarks a missing child. This lesson'sTreeNodeusesnullfor an absent left or right child, so comparing with==againstnullis how the base case recognises an empty subtree.
Complexity
Time: O(n) for n nodes. Each node triggers one real call of dfs, plus one more call for each missing child, and the total number of calls is at most 2n + 1. Appending to the buffer is constant time on average.
Space: O(n) for the result, and O(h) extra for the call stack, where h is the height of the tree. A balanced tree has a height around log n, while a tree that is one long chain has a height of n.
Edge cases and common mistakes
- Empty tree. With a
nullroot,dfsreturns at once and the method returns an empty array. - Single node. Both subtrees are empty, so the result is just the node's value.
- Wrong position of the append. Putting
result += root.valuebefore the left call gives preorder, and putting it after the right call gives postorder. For the example, those would give[1, 2, 3]and[3, 2, 1]. - Forgetting the base case. Without the
nullcheck, the first leaf's missing child causes aNullPointerExceptiononroot.left. - Very deep trees. Each level of the tree uses one stack frame. A left chain of a few thousand nodes is fine, but a chain of hundreds of thousands can overflow the stack with a
StackOverflowError; the exact depth depends on the JVM's stack size. That is the practical reason for the iterative follow-up, where an explicit stack of nodes replaces the call stack. - Creating a new buffer in each call. If
dfsmade its own buffer and returned it, the code would have to concatenate three pieces at every node. Passing one shared buffer is simpler and faster.
Testing
- Root 1 with a right child 2 whose left child is 3 gives
[1, 3, 2]. - A
nullroot gives[]. - Root 5 with left child 3 (children 1 and 4) and right child 8 gives
[1, 3, 4, 5, 8]. This is a binary search tree, so the output is sorted.
