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 C# DSA implementation can be compared directly with the rest of the DSA track.

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

Complexity

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

Implementation notes

  • Render tree structure explicitly instead of printing node objects.
  • The replay highlights the node, traversal state, queue, path, or search cursor that changes at each step.
binary search tree Values smaller than a node go left; larger values go right.