Implement a Binary Search Tree Fast AF

A binary search tree (BST) is a data structure that allows for efficient searching and insertion of elements. It works by organizing data in a tree-like structure, where each node has at most two children. The left child of a node contains a value that is smaller than the parent node, and the right child contains a value that is greater.

To implement a BST in Swift, we first need to create a node class that will represent each element in the tree. Each node should have a value and a reference to its left and right children. We can do this by creating a class called “Node” with three properties:

class Node {
  var value: Int
  var left: Node?
  var right: Node?

  init(value: Int) {
    self.value = value
  }
}

Next, we need to create a BST class that will store the root node of the tree and provide methods for inserting and searching for elements. We can do this by creating a class called “BinarySearchTree” with two methods: “insert” and “search”.

The “insert” method will take in a value and insert it into the correct position in the tree. We can do this by creating a new node with the value and traversing the tree to find the correct position to insert it. If the value is less than the current node, we move to the left child. If the value is greater, we move to the right child. If there are no children, we insert the new node as the child.

class BinarySearchTree {
  var root: Node?

  func insert(value: Int) {
    let newNode = Node(value: value)

    if root == nil {
      root = newNode
      return
    }

    var currentNode = root
    while currentNode != nil {
      if value < currentNode!.value {
        if currentNode?.left == nil {
          currentNode?.left = newNode
          return
        }
        currentNode = currentNode?.left
      } else {
        if currentNode?.right == nil {
          currentNode?.right = newNode
          return
        }
        currentNode = currentNode?.right
      }
    }
  }

The “search” method will take in a value and return a boolean indicating whether the value is present in the tree. We can do this by traversing the tree in a similar way as the insert method. If the value is found, we return “true”. If we reach a leaf node and the value is not found, we return “false”.

func search(value: Int) -> Bool {
    var currentNode = root
    while currentNode != nil {
      if value < currentNode!.value {
        currentNode = currentNode?.left
      } else if value > currentNode!.value {
        currentNode = currentNode?.right
      } else {
        return true
      }
    }
    return false
  }
}

Now that we have our BST class implemented, we can create a new instance and insert some values into it. For example:

let bst = BinarySearchTree()
bst.insert(value: 5)
bst.insert(value: 3)
bst.insert(value: 7)
bst.insert(value: 2)