Trees

BST Insert

Insert values into a binary search tree by comparing at each node.

Algorithm

Basic Implementation

basic.cpp 
#include <iostream>
#include <queue>
#include <sstream>
#include <string>
#include <vector>
using namespace std;
struct Node { int value; Node* left; Node* right; Node(int v, Node* l=nullptr, Node* r=nullptr): value(v), left(l), right(r) {} };
string render(Node* node) {
    if (node == nullptr) return "_";
    if (node->left == nullptr && node->right == nullptr) return to_string(node->value);
    return to_string(node->value) + "(" + render(node->left) + "," + render(node->right) + ")";
}
Node* sampleTree() {
    return new Node(4, new Node(2, new Node(1), new Node(3)), new Node(6, new Node(5), new Node(7)));
}
string listString(const vector<int>& values) {
    stringstream out; out << "[";
    for (size_t i = 0; i < values.size(); i++) { if (i) out << ", "; out << values[i]; }
    out << "]"; return out.str();
}
Node* insert(Node* root, int value) { if (!root) return new Node(value); if (value < root->value) root->left = insert(root->left, value); else root->right = insert(root->right, value); return root; }
int main() { Node* root = nullptr; for (int value : {4, 2, 6, 1, 3, 5, 7}) root = insert(root, value); cout << render(root) << "\n"; }

BST insertion is a comparison path. The pinned tree 4(2(1,3),6(5,7)) is shown with the inserted value taking its sorted slot.

Step 1 - Start at root

For value 5, compare with 4 first; 5 is larger, so move right.

First comparison: 5 > 4, so the search for the insert slot goes right.insert 54compare26137

Step 2 - Take the left slot under 6

At 6, value 5 is smaller, so it becomes the left child.

Second comparison: 5 < 6, so the open left slot is used.426compare135new7

Step 3 - Canonical tree

The resulting tree is the pinned shape 4(2(1,3),6(5,7)).

Final BST after 5 is present under 6.4261357

Complexity

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

Implementation notes

  • In C++, each node is a struct Node with int value plus raw Node* left and Node* right child links defaulting to nullptr.
  • insert(Node* root, int value) returns the subtree root. A null subtree allocates with new Node(value); otherwise recursion rewrites root->left or root->right with the returned child pointer.
  • The branch condition is value < root->value; equal values would take the else path to the right, though the checked trace inserts distinct values.
  • The executable builds from root = nullptr using values {4, 2, 6, 1, 3, 5, 7}. The trace shows paths such as 4 -> left -> 2 -> right before the tree reaches 4(2(1,3),6(5,7)).
  • render(Node*) recursively formats null children as _ and prints the final tree with std::cout << render(root) << "\n".
  • Visible allocation is one heap-allocated Node per inserted value. The source uses raw pointers, not smart pointers, and does not show a matching delete cleanup path.
  • The replay also includes the sorted insert contrast 1(_,2(_,3(_,4))), showing the unbalanced raw-link shape and height 4.
binary search tree Values smaller than a node go left; larger values go right.