What is the BST inorder algorithm?
The inorder algorithm returns values in ascending order (sorted from smallest to the largest value).
Code example
final class BSTNode<Value: Comparable> {
var val: Value?
var left: BSTNode?
var right: BSTNode?
init(val: Value? = nil) {
self.val = val
}
func inorder(_ visited: inout [Value]) -> [Value] {
if self.left != nil {
self.left!.inorder(&visited)
}
if self.val != nil {
visited.append(self.val!)
}
if self.right != nil {
self.right!.inorder(&visited)
}
return visited
}
}
Implementation
The inorder algorithm:
- Recursively traverse the
left
subtree. - Visit the current node.
- Recursively traverse the
right
subtree.
Time/Space complexity
The time complexity of the inorder 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).