What is the postorder algorithm?
The postorder algorithm, similar to the preorder algorithm, returns a list of values in the order they are visited.
Code Example
final class BSTNode<Value: Comparable> {
var val: Value?
var left: BSTNode?
var right: BSTNode?
init(val: Value? = nil) {
self.val = val
}
func postorder(_ visited: inout [Value]) -> [Value] {
if self.left != nil {
self.left!.postorder(&visited)
}
if self.right != nil {
self.right!.postorder(&visited)
}
if self.val != nil {
visited.append(self.val!)
}
return visited
}
}
Implementation
The postorder algorithm:
- Recursively traverse the current node’s
left
subtree. - Recursively traverse the current node’s
right
subtree. - Visit the current node.
Time/Space Complexity
- The time complexity of the postorder algorithm is O(N), where N is the total number of nodes.
- The space complexity:
- O(1) if recursion stack space is not considered.
- Otherwise, O(H), where H is the height of the tree.
- In the worst case, H can be the same as N (when the tree is skewed).
- In the best case, H can be the same as logN (when the tree is complete).