Problem overview
The function post_order_traversal receives the root of a binary tree and returns the node values in post order: the whole left subtree, then the whole right subtree, and the node itself last. The root is an Option<Box<TreeNode>>, which is None for an empty tree. A node has a val and two children, left and right, of the same Option<Box<TreeNode>> type.
For the tree with root 1, no left child, and a right child 2 that has a left child 3, the answer is [3, 2, 1]. Node 3 comes first because it is the only thing in 2's left subtree, then 2 itself, then the root. For the tree with root 1, children 2 and 3, and 2's children 4 and 5, the answer is [4, 5, 2, 3, 1].
Approach: recursion mirrors the definition
The order is defined recursively, so the code can follow the definition directly. To list a subtree in post order:
- list its left subtree;
- list its right subtree;
- list the node's own value.
An empty subtree lists nothing, which is the base case that ends the recursion. Putting the node's value after both recursive calls is what makes it post order. Putting it before them would give pre order, and putting it between them would give in order.
Instead of returning a new vector from every call and joining them, one vector is shared. The helper receives a mutable reference to it and pushes values as it goes. Everything is appended in the right order without any copying of partial results.
The lesson has a second solution for the same problem, which replaces the recursion with an explicit stack. This one is the shortest and most direct.
Step by step
- Create the output in
post_order_traversal:let mut result = Vec::new();. Rust works out the element type,i32, from how it is used. - Call the helper with
Self::dfs(root, &mut result)and end the function withresult, without a semicolon, to return it. Passing&mut resultlets the helper push into the vector while this function keeps ownership. - Declare
dfswith the parametersroot: Option<Box<TreeNode>>andresult: &mut Vec<i32>. It returns nothing. - Handle the empty case with
if let Some(node) = root. The block runs only when there is a node. ForNonenothing happens, so the recursion stops at missing children without separate checks. - Recurse left with
Self::dfs(node.left, result). - Recurse right with
Self::dfs(node.right, result). - Record the node by pushing
node.val, after both recursive calls.
The solution in Rust
impl Solution {
fn post_order_traversal(root: Option<Box<TreeNode>>) -> Vec<i32> {
let mut result = Vec::new();
Self::dfs(root, &mut result);
result
}
fn dfs(root: Option<Box<TreeNode>>, result: &mut Vec<i32>) {
if let Some(node) = root {
Self::dfs(node.left, result);
Self::dfs(node.right, result);
result.push(node.val);
}
}
}
Rust details that matter here:
- The helper takes the tree by value.
rootis an ownedOption<Box<TreeNode>>, soif let Some(node) = rootmoves the box intonode. The tree is consumed: after the call, the caller no longer has it. That is fine for a function that is handed the only copy of the tree. - Moving the children out of the box.
node.leftandnode.rightare moved into the recursive calls, which is allowed for the fields of aBox.node.valis ani32, which isCopy, so it can still be read after the two moves. That is whyresult.push(node.val)compiles on the last line. - Passing
resultalong. The parameter is already a&mut Vec<i32>. WritingSelf::dfs(node.left, result)reborrows it for the duration of the call, and thenresultis usable again for the next call and for thepush. No&mutis added at those call sites. Self::dfs. The helper has noselfparameter, so it is an associated function, called through the type.SelfmeansSolutioninside theimplblock.- Tail expression.
resulton its own line, without a semicolon, is the function's return value.
Complexity
Time: O(n). Each node is visited exactly once, and each visit does one push. Missing children are visited too, but there are at most n + 1 of them.
Space: O(h) extra, plus the O(n) output. The call stack is as deep as the tree is tall, h. For a balanced tree that is about log n, and for a tree where every node has one child it is n.
Edge cases and common mistakes
- Empty tree. A
Noneroot skips theif letblock and the function returns an empty vector,[]. - A single node. Both recursive calls get
None, so the result is just that node's value. - Wrong position of the push. Moving
result.push(node.val)above the recursive calls gives pre order. For the tree with root 1, children 2 and 3, and 2's children 4 and 5, that would print[1, 2, 4, 5, 3]instead of[4, 5, 2, 3, 1]. - Visiting right before left. That would produce a mirror order. Post order is defined with the left subtree first.
- Using the tree after the call. Because
dfstakes ownership, trying to userootagain afterSelf::dfs(root, &mut result)is a compile error about a moved value. A version that borrows the tree with&Option<Box<TreeNode>>would keep it usable. - Very deep trees. Recursion depth equals the height of the tree, so a very long chain uses a lot of stack. The lesson's second solution uses an explicit stack to avoid that.
Testing
- Root 1, right child 2, and 2's left child 3:
[3, 2, 1]. - Root 1, children 2 and 3, 2's children 4 and 5:
[4, 5, 2, 3, 1]. - An empty tree:
[].
