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:

  1. Recursively traverse the current node’s left subtree.
  2. Recursively traverse the current node’s right subtree.
  3. 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).

Thank you for reading! 😊