Problem overview
The method PostOrderTraversal receives the root of a binary tree and returns a List<int> with the node values in post order: the left subtree first, then the right subtree, and the node itself last. A node's value therefore always comes after the values of all its descendants.
In the example, the root 1 has no left child, and its right child 2 has a left child 3. Post order visits 3 first because it is the deepest node on the path. Then it visits 2, whose subtrees are both done, and finally 1. The output is [3, 2, 1].
Approach: let recursion handle the subtrees
A tree is defined recursively: every child of a node is the root of a smaller tree. So the traversal of a tree is the traversal of its left subtree, followed by that of its right subtree, followed by the node's own value. The same three lines work at every node.
The lesson collects the values in a single shared list that is passed down through every call. Each call adds to that one list, so nothing has to be merged on the way back up. The statement's follow up asks for an iterative version too. That one is the second lesson on this problem. The recursive solution is the shortest and the best starting point.
The three traversal orders differ only in when the node is handled relative to its two recursive calls. Before both calls is pre order, between them is in order, and after both is post order.
Step by step
- Write the public method first. Create the list
resultwithnew List<int>(), call the helperDfs(root, result)to fill it, and return it. The helper doesn't exist yet, but this shows how it will be used. - Declare the helper above
PostOrderTraversalaspublic void Dfs(TreeNode root, List<int> result). It returns nothing, because its job is to add values to the list it receives. - Stop at an empty subtree. If
rootisnull, return immediately. Every missing child reaches the helper as anull, so this one check is the base case that ends the recursion. - Visit the left subtree with
Dfs(root.left, result). All of its values are appended before anything else. - Visit the right subtree with
Dfs(root.right, result). These values follow the left ones. - Record the node last with
result.Add(root.val). Because this line comes after both calls, the node follows all its descendants.
The solution in C#
class Solution {
public void Dfs(TreeNode root, List<int> result) {
if (root == null) {
return;
}
Dfs(root.left, result);
Dfs(root.right, result);
result.Add(root.val);
}
public List<int> PostOrderTraversal(TreeNode root) {
List<int> result = new List<int>();
Dfs(root, result);
return result;
}
}
A few C# details:
- Fields of
TreeNode. In this lesson the node's fields are lowercase:val,leftandright. The helper and the public method use PascalCase, which is the usual C# convention for methods. - Lists are reference types.
Dfsreceives a reference to the caller's list, not a copy. Adding to it insideDfschanges the list thatPostOrderTraversalreturns, so the helper needs no return value. nullchecks.root == nullis the way to test for a missing node. Readingroot.valon anullreference would throw aNullReferenceException, so the check has to come first.- Bare
return. In avoidmethod,return;just ends the call.
Complexity
Time: O(n). Each node is visited once and does a constant amount of work: a null check, two calls and one Add. The calls on missing children are also constant, and there are at most n + 1 of them.
Space: O(h) for the call stack, plus the output. The recursion goes as deep as the tree is tall, h. For a balanced tree that is about log n, and for a tree that is a single chain it is n. The result list holds n values, which is needed in any solution.
Edge cases and common mistakes
- An empty tree. With
rootequal tonull, the first call returns at once and the method returns an empty list, notnull. - A single node. Both recursive calls hit the base case, then the node's value is added. The result is a list with one element.
- Moving the
Addline. Placing it before the recursive calls gives pre order, and placing it between them gives in order. For the example tree, pre order would give[1, 2, 3]and in order[1, 3, 2]. - Creating a new list in every call. If each call made its own list, the values would be lost or would need merging. Passing the same list down avoids that.
- Skipping the null check. Without it, the first leaf would call
Dfs(null, result)and crash onroot.left. - Very deep trees. A very long chain of nodes can exhaust the call stack in a recursive solution. The iterative version avoids this.
Testing
- The tree
[1, null, 2, 3]gives[3, 2, 1]. - A single node
[7]gives[7]. - An empty tree gives
[]. - The tree
[1, 2, 3](root 1 with children 2 and 3) gives[2, 3, 1].