Trees

BST Search

Search a binary search tree for one present and one absent value.

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 bool Search(Node? root, int target) { var node = root; while (node != null) { if (target == node.Value) return true; node = target < node.Value ? node.Left : node.Right; } return false; }
    static void Main() { var root = SampleTree(); Console.WriteLine(Search(root, 5) ? "5 found" : "5 not found"); Console.WriteLine(Search(root, 8) ? "8 found" : "8 not found"); }
}

Complexity

  • Time: O(h) per search
  • Space: O(1) iterative

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.
search path A comparison chooses one subtree at each step, so whole branches are skipped.