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
The tree owns its allocated nodes and deletes them in an iterative destructor, avoiding recursive cleanup on a skewed chain. Copying is disabled to prevent duplicate ownership of the same raw pointers. search returns a borrowed BinaryNode pointer that must not outlive the tree. Insertions preserve existing node allocations, but the class offers neither removal nor automatic balancing in this excerpt.
Complete implementation
struct BinaryNode {
int data;
BinaryNode* left;
BinaryNode* right;
BinaryNode(int x) : data(x), left(nullptr), right(nullptr) {}
};
class BinarySearchTree {
public:
BinarySearchTree(const BinarySearchTree&) = delete;
BinarySearchTree& operator=(const BinarySearchTree&) = delete;
~BinarySearchTree() {
while (root) {
if (root->left) {
auto node = root->left;
root->left = node->right;
node->right = root;
root = node;
} else {
auto node = root;
root = root->right;
delete node;
}
}
}
BinarySearchTree() = default;
BinaryNode* root = nullptr;
BinarySearchTree& insert(int data) {
BinaryNode* node = new BinaryNode(data);
// First insert becomes root
if (root == nullptr) {
root = node;
return *this;
}
BinaryNode* currentNode = root;
while (true) {
if (data < currentNode->data) {
// Insert the node if you reach a leaf and return
if (currentNode->left == nullptr) {
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 == nullptr) {
currentNode->right = node;
return *this;
}
// Continue by traversing right
currentNode = currentNode->right;
}
}
}
BinaryNode* search(int data) {
if (!root) {
return nullptr;
}
BinaryNode* currentNode = root;
while (currentNode) {
if (data < currentNode->data) {
currentNode = currentNode->left;
} else if (data > currentNode->data) {
currentNode = currentNode->right;
} else if (currentNode->data == data) {
return currentNode;
}
}
return nullptr;
}
};
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.