Trees

BST Insert

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

Algorithm

Basic Implementation

basic.cs 
using System;
using System.Collections.Generic;
using System.Linq;

class Node {
    public int Value;
    public Node? Left;
    public Node? Right;
    public Node(int value, Node? left = null, Node? right = null) { Value = value; Left = left; Right = right; }
}
class Program {
    static string Render(Node? node) {
        if (node == null) return "_";
        if (node.Left == null && node.Right == null) return node.Value.ToString();
        return $"{node.Value}({Render(node.Left)},{Render(node.Right)})";
    }
    static Node SampleTree() => new Node(4, new Node(2, new Node(1), new Node(3)), new Node(6, new Node(5), new Node(7)));
    static string ListString(IEnumerable<int> values) => "[" + string.Join(", ", values) + "]";
    static Node Insert(Node? root, int value) { if (root == null) return new Node(value); if (value < root.Value) root.Left = Insert(root.Left, value); else root.Right = Insert(root.Right, value); return root; }
    static void Main() { Node? root = null; foreach (var value in new[] {4, 2, 6, 1, 3, 5, 7}) root = Insert(root, value); Console.WriteLine(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

  • Render tree structure explicitly instead of printing node objects.
  • Node is a class, so Left and Right hold managed references that may be null; new Node(value) allocates through the CLR and is reclaimed by GC. The recursive Insert returns the subtree root after updating one nullable child link, and duplicate values follow the else branch to the right.
  • The executable builds the canonical balanced tree. The replay also includes a sorted-order contrast where height grows to 4, showing why an unbalanced BST can degrade to O(n) without rotation.
binary search tree Values smaller than a node go left; larger values go right.