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.
Kotlin example and implementation choices
Nullable BinaryNode links represent absent children. Insert returns this tree, preserving the fluent API without constructing another owner or copy. Search returns BinaryNode? rather than a payload sentinel. The mutable node fields make ordering an invariant maintained by convention and methods, not by the type system alone. Equal Int keys go right, and no rotation repairs a skewed tree.
Complete implementation
class BinaryNode(var data: Int) {
var left: BinaryNode? = null
var right: BinaryNode? = null
}
class BinarySearchTree {
var root: BinaryNode? = null
fun insert(data: Int): BinarySearchTree {
val node = BinaryNode(data)
val rootNode = root
// First insert becomes root
if (rootNode == null) {
root = node
return this
}
var currentNode: BinaryNode = rootNode
while (true) {
if (data < currentNode.data) {
// Insert the node if you reach a leaf and return
val leftNode = currentNode.left
if (leftNode == null) {
currentNode.left = node
return this
}
// Continue by traversing left
currentNode = leftNode
} else {
// Insert the node if you reach a leaf and return
val rightNode = currentNode.right
if (rightNode == null) {
currentNode.right = node
return this
}
// Continue by traversing right
currentNode = rightNode
}
}
}
fun search(data: Int): BinaryNode? {
if (root == null) {
return null
}
var currentNode = 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 Kotlin
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 Kotlin 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 Kotlin interview preparation guide connects these language choices with further practice and the cross-language operation reference.