Trees

BST Insert

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

Algorithm

The canonical tree is 4(2(1,3),6(5,7)), so this Swift DSA implementation can be compared directly with the rest of the DSA track.

binary search tree Values smaller than a node go left; larger values go right.

Visual walkthrough

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

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

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