Traverse

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: ...

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! 😊

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, append val to the visited array. The second step is to check if the left node exists. If it does, recursively call the preorder method on the left 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). Thank you for reading! 😊