Problem overview
The function postOrderTraversal receives the root of a binary tree and returns the values of its nodes in post order: first the whole left subtree, then the whole right subtree, and the node itself last. The root is a TreeNode?, which is null for an empty tree, and the result is a List<Int>. A node stores its number in value and its children in left and right, either of which can be null.
In the example, the root 1 has no left child and a right child 2, and 2 has a left child 3:
1
\
2
/
3
Post order visits 3 first, because it is the deepest node on the way down. Then it finishes 2 and finally 1, so the answer is [3, 2, 1].
Approach: let the recursion do the bookkeeping
A tree is made of smaller trees: every child is the root of a subtree. So the traversal of a tree is defined by the traversal of its two subtrees, and post order says exactly how to combine them:
- traverse the left subtree;
- traverse the right subtree;
- record the node's own value.
Moving step 3 changes the order and nothing else. Recording the value first gives pre order, recording it between the two subtrees gives in order. The empty tree is the base case: it has nothing to record, so the recursion stops there.
Instead of building and merging many small lists, the solution passes one shared list down the recursion, and every call appends to the end of it. Because the appends happen in the order the calls finish, the list ends up in post order.
For the example, the calls run like this:
dfs(1)
dfs(null) left of 1, nothing to add
dfs(2)
dfs(3)
dfs(null) left of 3
dfs(null) right of 3
add 3
dfs(null) right of 2
add 2
add 1
The additions happen in the order 3, 2, 1.
This lesson is the recursive version. The same traversal can be done iteratively with an explicit stack, which avoids deep recursion; the second lesson on this problem does that.
Step by step
- Write
postOrderTraversalfirst, assuming a helperdfs(root, result)exists. It creates an empty mutable list, calls the helper to fill it, and returns it. - Declare the helper above it with the parameters
root: TreeNode?andresult: MutableList<Int>. The root is nullable because the recursion also visits missing children. - Check for
nullfirst and return at once. This is the base case and it is what stops the recursion at the bottom of the tree. - Recurse into the left child with the same list.
- Recurse into the right child with the same list. Neither call needs its own null check, because the first line of the helper handles it.
- Add the node's value last, after both recursive calls. That position is what makes it post order.
The solution in Kotlin
class Solution {
fun dfs(root: TreeNode?, result: MutableList<Int>) {
if (root == null) {
return
}
dfs(root.left, result)
dfs(root.right, result)
result.add(root.value)
}
fun postOrderTraversal(root: TreeNode?): List<Int> {
val result = mutableListOf<Int>()
dfs(root, result)
return result
}
}
The Kotlin details worth knowing:
- Nullable types and smart casts.
TreeNode?means "aTreeNodeornull". Writingroot.leftdirectly on it would not compile. After theif (root == null) return, the compiler knowsrootis not null for the rest of the function, soroot.left,root.rightandroot.valueneed no?.or!!. This works becauserootis a function parameter, which can't be reassigned. - The helper returns nothing. A function with no declared return type returns
Unit, and the barereturnsimply ends the call. All results travel throughresult. - Shared mutable list.
MutableList<Int>is passed as a reference to one list, so the appends made inside deeper calls are visible to the caller. The recursion never creates a second list. valversus mutability.val resultonly means the name can't be reassigned. The list can still grow, which is whymutableListOf<Int>()is needed. The plainlistOfwould not offeradd.- Returning a read-only type. The function is declared to return
List<Int>, a read-only view. Returning theMutableListis fine, because a mutable list is also aList. - Type argument.
mutableListOf<Int>()needs the explicit<Int>, as the empty call gives the compiler nothing to infer from.
Complexity
Let n be the number of nodes and h the height of the tree.
Time: O(n). The helper runs once for each node and once for each missing child. A tree with n nodes has n + 1 empty child slots, so the number of calls is about 2n + 1, and each call does a constant amount of work. Appending to a MutableList is amortized constant time.
Space: O(h) for the call stack, plus the O(n) result. At any moment the open calls form a path from the root down to the current node. That path is about log n long for a balanced tree and as long as n for a tree that is a single chain. A very long chain can overflow the default JVM stack, which is the reason for the iterative follow-up.
Edge cases and common mistakes
- Empty tree. A
nullroot returns an empty list: the helper returns immediately and nothing is added. - Single node. The result is a list with just that value.
- A node with one child. In the example, node 1 has only a right child. The missing left child is passed to the helper and ignored by the null check, so no special handling is needed.
- Adding the value too early. Moving
result.add(root.value)to the top of the helper gives pre order,[1, 2, 3]for the example. - Swapping the two calls. Visiting the right subtree before the left one gives a mirrored order. On the seven-node tree from the testing list, it would produce
[7, 6, 3, 5, 4, 2, 1]instead of[4, 5, 2, 6, 7, 3, 1]. - Creating a new list in each call. A fresh list per recursion would force you to merge lists on the way back up. Passing one list down is simpler and avoids the copying.
Testing
- The example tree,
[1, null, 2, 3]in level order, gives[3, 2, 1]. - A full tree of seven nodes,
[1, 2, 3, 4, 5, 6, 7]in level order, gives[4, 5, 2, 6, 7, 3, 1]. - A single node
[1]gives[1]. - An empty tree gives
[].