Step by step · Python, C++ and Java

Binary search tree insertion, visualized

A binary search tree keeps every value in a node’s left subtree smaller than it, and every value in its right subtree larger. That one rule makes search, insert and delete take time proportional to the tree’s height.

How it works

class TreeNode:
    def __init__(self, val):
        self.val = val
        self.left = None
        self.right = None


def insert(node, val):
    if node is None:
        return TreeNode(val)
    if val < node.val:
        node.left = insert(node.left, val)
    elif val > node.val:
        node.right = insert(node.right, val)
    return node


root = None
for value in [50, 30, 70, 20, 40, 60, 80]:
    root = insert(root, value)

print("built")

#include <iostream>

struct TreeNode {
    int val;
    TreeNode* left;
    TreeNode* right;
    TreeNode(int v) : val(v), left(nullptr), right(nullptr) {}
};

TreeNode* insert(TreeNode* root, int value) {
    if (root == nullptr) {
        return new TreeNode(value);
    }
    if (value < root->val) {
        root->left = insert(root->left, value);
    } else {
        root->right = insert(root->right, value);
    }
    return root;
}

int main() {
    TreeNode* root = new TreeNode(8);
    insert(root, 3);
    insert(root, 10);
    insert(root, 1);
    insert(root, 6);

    std::cout << root->left->val << std::endl;
    return 0;
}

public class Main {
    static class TreeNode {
        int val;
        TreeNode left;
        TreeNode right;

        TreeNode(int val) {
            this.val = val;
        }
    }

    public static void main(String[] args) {
        TreeNode root = null;
        int[] values = {50, 30, 70, 20, 40, 60};

        for (int value : values) {
            root = insert(root, value);
        }

        System.out.println(root.val);
    }

    static TreeNode insert(TreeNode node, int val) {
        if (node == null) {
            return new TreeNode(val);
        }
        if (val < node.val) {
            node.left = insert(node.left, val);
        } else if (val > node.val) {
            node.right = insert(node.right, val);
        }
        return node;
    }
}

How binary search tree insertion works

To insert, start at the root and compare: smaller goes left, larger goes right, until you reach an empty child, where the new node is attached. The recursive version returns the subtree’s root at every level, so each parent re-links its child on the way back up.

The Python example inserts 50, 30, 70, 20, 40, 60, 80, which produces a perfectly balanced tree three levels deep.

What to watch for when it runs

The path each value takes down from the root is highlighted as it descends.
New nodes only ever appear as leaves — insertion never rearranges existing nodes.
Insert the same values in sorted order and the tree degenerates into a chain, making every operation O(n).

Time and space complexity

Time: O(h) per insert — O(log n) balanced, O(n) worst case
Space: O(h) recursion

h is the height of the tree. Self-balancing trees (AVL, red-black) exist to keep h at O(log n) whatever order values arrive in.

Stuck on your own version?

Paste it into the visualizer and watch your own code run, line by line — bugs included.

How binary search tree insertion works

What to watch for when it runs

Time and space complexity

Related visualizations

Stuck on your own version?