Problem overview
The method postOrderTraversal receives the root of a binary tree and returns the values of its nodes in post order as an Array[Int]. Post order visits the left subtree first, then the right subtree, and the node itself last.
For the tree whose root holds 1, with no left child and a right child 2 that has a left child 3, the result is Array(3, 2, 1). Node 3 is the only thing in the left subtree of 2, so it comes first. Then comes 2, whose subtrees are done, and the root 1 comes last. A bigger example: for the root 1 with the left child 2 (children 4 and 5) and the right child 3 (right child 6), the result is Array(4, 5, 2, 6, 3, 1).
Approach: recursion that records the node last
A tree is a node with two smaller trees under it, or nothing at all. That shape suggests recursion. To list a subtree in post order, list its left subtree, list its right subtree, then add the node's own value. A missing child is an empty subtree and contributes nothing, so a null check ends the recursion.
The recursive helper dfs(root, result) doesn't return a list. It appends to one shared ArrayBuffer, which the main method creates, passes down and converts at the end. This avoids building and concatenating many small lists.
Only the position of the "record the value" line differs between the three classic orders: before the recursive calls it gives pre order, between them in order, after them post order. A second lesson on this problem solves it without recursion, using an explicit stack.
Step by step
- In
postOrderTraversal, createval resultas an emptyArrayBuffer[Int], calldfs(root, result)to fill it, and end withresult.toArray, because the method returns anArray[Int]. - Declare the helper
dfswith the parametersroot: TreeNodeandresult: ArrayBuffer[Int]. It returnsUnit: its output is what it adds to the buffer. - Stop at an empty subtree. If
root == null, return at once. A missing child isnullin the lesson'sTreeNodeclass. - Visit the left subtree with
dfs(root.left, result). No check onroot.leftis needed, because the first line of the helper handlesnull. - Visit the right subtree with
dfs(root.right, result). - Record the node with
result += root.value, after both calls. This position is what makes the order post order.
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)
dfs(root.right, result)
result += root.value
}
def postOrderTraversal(root: TreeNode): Array[Int] = {
val result = scala.collection.mutable.ArrayBuffer[Int]()
dfs(root, result)
result.toArray
}
}
Scala details:
ArrayBufferversusArray. AnArrayhas a fixed size, while anArrayBuffergrows as values are appended with+=. The method must return anArray[Int], sotoArraymakes the final copy.- The buffer is shared. Every recursive call receives the same object, so appending in a deep call is visible to the caller. That is why
dfscan returnUnit. - A bare
returnin a method that returnsUnitsimply ends the call. It sits at the method's own level here, not inside a closure, so it is an ordinary return. - The last expression is the result.
result.toArrayneeds noreturn. - Comparing with
null.root == nullis a safe comparison in Scala:==compares values and handlesnullwithout throwing. - Printing the result.
printlnof anArrayshows an object reference, not the values. UsemkString(", ")to look at them.
Complexity
Time: O(n). Each node is visited once, and each visit does a constant amount of work. The calls on null children add at most n + 1 more constant-time calls.
Space: O(h) for the recursion plus O(n) for the result, where h is the height of the tree. The call stack is as deep as the longest path from the root. For a balanced tree h is about log n, and for a tree that is a single chain it is n. The JVM's stack is limited: a chain of a few thousand nodes is fine, but a very deep one, such as 100,000 nodes, typically ends in a StackOverflowError; the exact limit depends on the stack size. The iterative version in the other lesson avoids that limit.
Edge cases and common mistakes
- Empty tree. With
root = null, the helper returns at once and the method returns an empty array. - Single node. The result is that node's value alone.
- Only one child. A node with only a right child still works: the left call hits
nulland returns, and the right subtree comes next. - Recording too early. Moving
result += root.valueabove the two calls gives pre order. For the first example that would be1, 2, 3instead of3, 2, 1. - Creating a new buffer in each call. If the helper made its own buffer, the values would stay in the callers' separate buffers and the final result would be empty or incomplete.
- Using the wrong field name. A node's number is read with
root.valuein this lesson.
Testing
- Root 1, right child 2, whose left child is 3:
Array(3, 2, 1). - Root 1 with left child 2 (children 4, 5) and right child 3 (right child 6):
Array(4, 5, 2, 6, 3, 1). null: an empty array.
