What is tree traversal?
Tree traversal, also known as “tree search” or “walking the tree,” is the process of visiting each node in a tree data structure exactly once.
What is the BST preorder algorithm?
The preorder algorithm returns a list of values in the order they are visited. It makes a copy that preserves the structure and recursively traverses the BST.
Code example
func preorder(_ visited: inout [Value]) -> [Value] {
if self.val != nil {
visited.append(self.val!)
}
if self.left != nil {
self.left!.preorder(&visited)
}
if self.right != nil {
self.right!.preorder(&visited)
}
return visited
}
Implementation
- The first step is to check if
val
exists. If it does, appendval
to thevisited
array. - The second step is to check if the
left
node exists. If it does, recursively call thepreorder
method on theleft
node. - The third step is similar to the second one but for the
right
node.
Time/Space Complexity
- The time complexity of the preorder algorithm is O(N), where N is the total number of nodes.
- The space complexity:
- O(1) if no recursion stack space is 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).