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:

  • Time Complexity is O(h), where h is the height of the tree.
  • Space Complexity is O(1).

Thank you for reading! 😊