Postorder

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). Thank you for reading! 😊