DSA - Binary Search Tree - Exists

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

September 28, 2024 · 2 min · Dmytro Chumakov

DSA - Binary Search Tree - Postorder

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

September 27, 2024 · 1 min · Dmytro Chumakov

DSA - Binary Search Tree - Traverse - Preorder

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

September 26, 2024 · 2 min · Dmytro Chumakov

DSA - Binary Search Tree - Delete

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

September 24, 2024 · 2 min · Dmytro Chumakov

DSA - Binary Search Tree Min/Max

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

September 22, 2024 · 2 min · Dmytro Chumakov