The implementation lesson builds a binary search tree with an insert method, a search method, and a retained root reference. It does not rebalance the tree. Both methods follow the ordering rule until they find a matching node or an absent child, so their running time depends on the resulting tree height.
Establish the root before following branches
An empty tree has no root. Its first insertion creates the root node. Later insertions compare the new value with the current node and select the appropriate child. Finding an absent child identifies the insertion position: attach the new node there and finish. Traversing both subtrees would ignore the search ordering that makes this structure useful.
For inserts 8, 3, 10, and 6, the value 6 follows left from 8 and right from 3. Its position must satisfy both comparisons. That complete path explains the inherited ordering condition; comparing only with the final parent is not the whole reasoning.
Search follows the same exclusion rule
Starting at the root, return the current node on a match. Otherwise select one child by comparison. If that child is absent, return the implementation's missing result. Check whether callers expect a node or its contained value; returning only data would change this lesson's API.
Test a root match, a leaf match, a missing value between existing keys, and targets outside the entire range. Decide how equal inserts behave before extending the example. A duplicate policy is part of the data structure, so insertion, search, and any later validation must agree.
Measure the path you actually built
Inserting sorted values into an unbalanced tree can create a chain. Each later insertion then walks farther, and a sequence of inserts can take quadratic total work. For a balanced shape, individual paths are logarithmic. The simple code does not establish that balance automatically.
An iterative implementation can retain only its current reference while searching. A recursive implementation also retains a call chain whose depth follows the path. Count the allocated nodes separately from that auxiliary work.
Open the current implementation, draw its shape after each insertion, then continue with BST Validate. Include an ancestor-bound violation in your tests so a locally plausible tree cannot pass unnoticed.
Use the implementation's duplicate rule
Insert 8, 3, 10, and 3. A smaller value follows the left link; every other value follows the right. The second 3 is therefore placed to the right of the first 3. In-order traversal yields [3, 3, 8, 10], preserving the duplicate. Searching for 3 returns a matching node without promising which duplicate it identifies.
This insertion policy differs from an exercise that requires every key to be unique and bounds both subtrees strictly. In particular, use the separate validation lesson's stated contract before applying its checks to a tree built by this class.
Relate insertion and search to shape
Both operations follow one downward path, taking O(h) time for height h. The class performs no rotations or balancing. Sorted input can build a chain with O(n) height, making a sequence of insertions quadratic overall. Calling it a binary search tree does not establish logarithmic worst-case operations.
The tree owns or retains O(n) nodes. Iterative search uses constant additional traversal state. Check empty search, root search, an absent value, duplicate insertion, and both increasing and decreasing insertion orders. The standalone code includes the BinaryNode definition so it can be compiled outside the course editor. Removal and balancing are outside this excerpt's API; adding either requires its own invariants and tests.
C# example and implementation choices
BinaryNode is a reference class with public integer and child fields. Insert returns the same BinarySearchTree instance, and Search returns a node reference or null. Equal keys follow the right branch during insertion. Garbage collection handles allocations without guaranteeing balanced shape. Consumers should not rewrite public child fields if they expect later searches to rely on the original ordering invariant.
Complete implementation
public class BinaryNode {
public int data;
public BinaryNode left;
public BinaryNode right;
public BinaryNode(int data) {
this.data = data;
this.left = null;
this.right = null;
}
}
public class BinarySearchTree {
public BinaryNode root;
public BinarySearchTree() {
this.root = null;
}
public BinarySearchTree Insert(int data) {
var node = new BinaryNode(data);
// First insert becomes root
if (this.root == null) {
this.root = node;
return this;
}
BinaryNode currentNode = this.root;
while (true) {
if (data < currentNode.data) {
// Insert the node if you reach a leaf and return
if (currentNode.left == null) {
currentNode.left = node;
return this;
}
// Continue by traversing left
currentNode = currentNode.left;
} else {
// Insert the node if you reach a leaf and return
if (currentNode.right == null) {
currentNode.right = node;
return this;
}
// Continue by traversing right
currentNode = currentNode.right;
}
}
}
public BinaryNode Search(int data) {
if (this.root == null) {
return null;
}
BinaryNode currentNode = this.root;
while (currentNode != null) {
if (data < currentNode.data) {
currentNode = currentNode.left;
} else if (data > currentNode.data) {
currentNode = currentNode.right;
} else if (currentNode.data == data) {
return currentNode;
}
}
return null;
}
}
Continue in C#
Open Implement a Binary Search Tree for the complete course explanation. The course keeps your saved programming-language choice. Use this standalone page to inspect the C# example and run it in your own local environment. Follow the original course sequence when you want the surrounding lesson context and related exercises.
The C# interview preparation guide connects these language choices with further practice and the cross-language operation reference.