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

What is a Queue? A Queue is an abstract data type that serves as an ordered collection of elements. A simple queue typically has several operations: push(item) - adds an item to the tail pop() - removes and returns an item from the head These operations make a queue a FIFO (First In, First Out) data structure. Implementation There are two ways to implement a queue. The first and simplest (but less efficient) way is by using an array and basic operations: ...