Trees

BST Insert

Insert values into a binary search tree by comparing at each node.

Algorithm

Basic Implementation

basic.swift 
final class Node {
    let value: Int
    var left: Node?
    var right: Node?
    init(_ value: Int, _ left: Node? = nil, _ right: Node? = nil) { self.value = value; self.left = left; self.right = right }
}
func render(_ node: Node?) -> String {
    guard let node = node else { return "_" }
    if node.left == nil && node.right == nil { return String(node.value) }
    return "\(node.value)(\(render(node.left)),\(render(node.right)))"
}
func sampleTree() -> Node {
    return Node(4, Node(2, Node(1), Node(3)), Node(6, Node(5), Node(7)))
}
func listString(_ values: [Int]) -> String { return "[" + values.map(String.init).joined(separator: ", ") + "]" }
func insert(_ root: Node?, _ value: Int) -> Node { guard let root = root else { return Node(value) }; if value < root.value { root.left = insert(root.left, value) } else { root.right = insert(root.right, value) }; return root }
var root: Node? = nil
for value in [4, 2, 6, 1, 3, 5, 7] { root = insert(root, value) }
print(render(root))

BST insertion is a comparison path. The pinned tree 4(2(1,3),6(5,7)) is shown with the inserted value taking its sorted slot.

Step 1 - Start at root

For value 5, compare with 4 first; 5 is larger, so move right.

First comparison: 5 > 4, so the search for the insert slot goes right.insert 54compare26137

Step 2 - Take the left slot under 6

At 6, value 5 is smaller, so it becomes the left child.

Second comparison: 5 < 6, so the open left slot is used.426compare135new7

Step 3 - Canonical tree

The resulting tree is the pinned shape 4(2(1,3),6(5,7)).

Final BST after 5 is present under 6.4261357

Complexity

  • Time: O(h) per insert
  • Space: O(n)

Implementation notes

  • final class Node gives each tree node reference semantics; value is a let Int, while left and right are mutable Node? child references.
  • init(_ value: Int, _ left: Node? = nil, _ right: Node? = nil) defaults new child links to nil.
  • insert(_ root: Node?, _ value: Int) -> Node handles an empty subtree with guard let root = root else { return Node(value) }.
  • Recursive insertion mutates child references in place: root.left = insert(root.left, value) for value < root.value, otherwise root.right = insert(root.right, value).
  • Equal values would follow the else branch to the right; the checked input has no duplicates.
  • var root: Node? = nil is reassigned after each insertion so the first returned node becomes the tree root.
  • The trace records insertion paths for 4, 2, 6, 1, 3, 5, 7, ending at 4(2(1,3),6(5,7)); the adversarial contrast shows sorted inserts [1, 2, 3, 4] forming 1(_,2(_,3(_,4))) with height 4.
  • render(_:) prints _ for nil children and nested node text, so print(render(root)) outputs 4(2(1,3),6(5,7)).
binary search tree Values smaller than a node go left; larger values go right.