DSA

Code Example final class BSTNode<Value: Comparable> { var val: Value? var left: BSTNode? var right: BSTNode? init(val: Value? = nil) { self.val = val } func exists(_ val: Value) -> Bool { // 1 guard let selfVal = self.val else { return false } // 2 if self.val == val { return true } // 3 if val < self.val! { if self.left == nil { return false } return self.left!.exists(val) } // 4 if self.right == nil { return false } // 5 return self.right!.exists(val) } } Implementation The exists algorithm: Check if self.val exists. If it does not exist, return false. If it does, move to the next step. Compare self.val with the input value. If the values are equal, return true. If they are not equal, move to the next step. If the input val is less than self.val, and the left node exists, return a recursive call of the exists method on the left node; otherwise, return false. If the input val is greater than self.val, move to the next step. Check if the right node exists. If it does not exist, return false. If it does exist, move to the next step. Return a recursive call of the exists method on the right node. Time/Space Complexity Time complexity: The time complexity of the exists algorithm is O(N), where N is the total number of nodes. 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 log N (when the tree is complete). Thank you for reading! 😊

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

Introduction The delete algorithm is perhaps one of the hardest parts of managing a binary search tree (BST). Code Example final class BSTNode { var val: Int? var left: BSTNode? var right: BSTNode? init(val: Int? = nil) { self.val = val } func delete(_ val: Int) -> BSTNode? { // 1 guard let selfVal = self.val else { return nil } // 2 if val < selfVal { if self.left == nil { return self } self.left = self.left!.delete(val) } // 3 if val > selfVal { if self.right == nil { return self } self.right = self.right!.delete(val) } // 4 if self.right == nil { return self.left } // 5 if self.left == nil { return self.right } // 6 var minLargerNode = self.right while minLargerNode?.left != nil { minLargerNode = minLargerNode?.left } guard let minLargerNode = minLargerNode else { return self } self.val = minLargerNode.val self.right = self.right?.delete(minLargerNode.val!) return self } } Implementation Let’s look at the details: ...

Introduction Finding the min and max elements is one of the simplest algorithms regarding BST (Binary Search Tree). The findMin method loops through the left child nodes and returns the value from the last node. The findMax method does the same but traverses the right child nodes. Code Example - Min func findMin() -> Int? { var min: Int? var curr: BSTNode? = self while curr != nil { min = curr?.val curr = curr?.left } return min } Code Example - Max func findMax() -> Int? { var max: Int? var curr: BSTNode? = self while curr != nil { max = curr?.val curr = curr?.right } return max } Complete Code Example final class BSTNode { var val: Int? var left: BSTNode? var right: BSTNode? init(val: Int? = nil) { self.val = val } func insert(_ val: Value) { if self.val == nil { self.val = val return } if self.val == val { return } if val < self.val! { if self.left != nil { self.left!.insert(val) return } else { self.left = BSTNode(val: val) return } } if self.right != nil { self.right!.insert(val) return } self.right = BSTNode(val: val) } func findMin() -> Int? { var min: Int? var curr: BSTNode? = self while curr != nil { min = curr?.val curr = curr?.left } return min } func findMax() -> Int? { var max: Int? var curr: BSTNode? = self while curr != nil { max = curr?.val curr = curr?.right } return max } } Time/Space Complexity For both findMin and findMax: ...