Insert into a binary search tree

You are midway through a technical screen at Oracle when the interviewer pulls up a binary search tree on the shared editor. "I want you to insert a value into this tree," they say, "but without rearranging any existing nodes." This problem, also known as "Insert into a Binary Search Tree" on other platforms, tests a fundamental operation that underpins how sorted data structures work. It is a staple in interviews at companies like Oracle and Cisco because it reveals whether you truly understand the BST property and can think recursively.

TL;DR

To insert a value into a BST, recursively traverse the tree using the BST ordering property: go left when the value is smaller than the current node, go right when it is larger. When you hit a null position, create a new node there and return it. Each recursive call reassigns the returned node to the appropriate child pointer, and the original root bubbles back up unchanged. This runs in O(h) time where h is the tree height, with O(h) space for the call stack.

Why This Problem Matters

BST insertion is one of the core operations you need to master for tree-based interview questions. It builds directly on BST search, and once you understand the insertion pattern, you can tackle deletion, validation, and balancing problems with confidence. Companies test this because it checks both your understanding of the BST invariant and your comfort with recursive tree manipulation.

Binary Search Trees: The Ordering Guarantee

A binary search tree is a binary tree with one critical constraint: for every node, all values in its left subtree are smaller, and all values in its right subtree are larger. This ordering guarantee is what makes search, insertion, and deletion efficient.

In the tree above, every node in the left subtree of 8 (nodes 1, 3, 5) has a value less than 8, and every node in the right subtree (10, 12, 14) has a value greater than 8. This invariant holds recursively at every node in the tree.

Understanding the Problem

Here is what we are working with:

Given: The root of a binary search tree and an integer n Task: Insert a new node with data = n into the tree Constraint: Do not modify the positions of existing nodes Guarantee: No node with data = n already exists in the tree

The example from the problem:

After inserting 6:

The value 6 lands as the right child of node 5 because 6 > 4 (go right), 6 < 8 (go left), and 6 > 5 (go right to a null position).

Edge Cases to Consider

1. Empty tree (null root): Return a new single-node tree
2. Single node: Insert as left or right child depending on comparison
3. Skewed tree: Insertion still works, just follows the single chain
4. Value fits at an internal gap: The algorithm always inserts as a leaf, preserving existing structure

Solution Approach

Since the problem asks us to preserve existing node positions, we need to add the new value as a leaf node. The BST property tells us exactly where that leaf goes: just follow the comparisons until you reach a null spot.

Walking Through the Algorithm

Let's trace inserting 6 into our example tree step by step.

Step 1: Start at the root (4). Since 6 > 4, we move to the right subtree.

Step 2: Now at node 8. Since 6 < 8, we move to the left subtree.

Step 3: Now at node 5. Since 6 > 5, we move right, but the right child is null. This is where our new node goes.

The Recursive Insight

The pattern here maps perfectly to recursion. At each node, we make a binary decision (go left or go right) and delegate the rest to a recursive call. The base case is simple: when we reach a null node, we have found the insertion point and return a new TreeNode.

The elegant part is the assignment pattern: root.left = insert(root.left, n). When the recursive call reaches null and returns a new node, that return value gets assigned as the child. When the subtree already exists, the recursive call just returns the existing subtree root unchanged.

Here is the full recursion trace for inserting 6:

Implementation

Prefer a different language? Jump to solutions in other languages.

public class Solution {
  public TreeNode insert(TreeNode root, int n) {
    // Base case: found the null spot, create the new node
    if (root == null) {
      return new TreeNode(n);
    }

    // BST property: smaller values go left
    if (n < root.data) {
      root.left = insert(root.left, n);
    }
    // Larger values go right
    else if (n > root.data) {
      root.right = insert(root.right, n);
    }

    // Return the (unchanged) root to maintain tree structure
    return root;
  }
}

Let's walk through the key decisions in this code:

1. Base case (root == null): We have traversed past a leaf. This null position is exactly where the new node belongs. We create and return it.

2. Go left (n < root.data): The new value is smaller than the current node, so it belongs somewhere in the left subtree. The assignment root.left = insert(root.left, n) handles both cases: if root.left is null, it gets the new node. If it already exists, the recursive call returns it unchanged.

3. Go right (n > root.data): Same logic, mirrored for the right subtree.

4. Return root: Each call returns the current node so the parent's assignment works correctly. The tree structure remains intact from top to bottom.

Complexity Analysis

Time Complexity: O(n) worst case, O(log n) average

The algorithm traverses a single path from the root to a leaf position. How long that path is depends on the tree's shape:

• Balanced BST: The height is roughly log(n), so insertion takes O(log n) time. Each comparison eliminates half the remaining nodes.
• Skewed BST: If the tree degenerates into a straight line (all left children or all right children), the height equals n, giving O(n) time.

In the worst case above, inserting 6 requires visiting all 5 existing nodes. This is why self-balancing BSTs (AVL, Red-Black) exist in production systems.

Space Complexity: O(n) worst case, O(log n) average

The recursive approach uses call stack space proportional to the tree height. For a balanced tree, that is O(log n). For a skewed tree, O(n). An iterative version can reduce this to O(1) by using a parent pointer instead of recursion, though the recursive version is cleaner and preferred in interviews.

Common Pitfalls

Here are mistakes I have seen candidates make with this problem:

1. Forgetting the assignment: Writing insert(root.left, n) without root.left = insert(root.left, n). The recursive call creates the node but never attaches it to the tree.

2. Modifying existing nodes: Some candidates try to find the parent and set its child directly. While this works iteratively, mixing it with recursion leads to confusing code.

3. Not returning root: Forgetting return root at the end means the parent call gets null or garbage, breaking the entire tree above the insertion point.

4. Handling duplicates: The problem guarantees no duplicates, but candidates sometimes add unnecessary duplicate-checking logic. Read constraints carefully.

Interview Tips

When you get this problem in an interview:

1. Clarify the BST property: Confirm that left children are strictly less than and right children are strictly greater than the parent. Ask about duplicates.

2. Start with the base case: "When root is null, I have found the spot for my new node." This anchors the entire solution.

3. Explain the assignment pattern: Walk through why root.left = insert(root.left, n) works for both the null case and the existing-subtree case. This shows deep understanding.

4. Discuss complexity trade-offs: Mention that a balanced BST gives O(log n) but a skewed tree degrades to O(n). If the interviewer asks about guarantees, bring up AVL or Red-Black trees.

5. Offer the iterative alternative: If asked, describe the iterative approach using a parent pointer. It saves stack space but the recursive version is the standard answer.

Related Problems and Practice

Once you are comfortable with BST insertion, these problems build on the same foundations:

• Find the minimum/maximum BST node: Same traversal pattern, always going left or right
• Validate a binary search tree: Uses the BST property in reverse, checking rather than exploiting it
• Delete a node from a BST: The harder counterpart to insertion, requiring restructuring
• Convert a binary tree to its mirror: Another recursive tree transformation

Consistent practice is the fastest path to interview confidence. This problem and hundreds of others are available on Firecode, where over 50,000 engineers have prepared for technical interviews and landed roles at top companies. Whether you are brushing up on BST fundamentals or working through advanced tree problems, building that muscle memory with daily practice makes all the difference.

Solutions in Other Languages

Python

class Solution:
    def insert(self, root, n):
        if root is None:
            return TreeNode(n)

        if n < root.data:
            root.left = self.insert(root.left, n)
        elif n > root.data:
            root.right = self.insert(root.right, n)

        return root

JavaScript

class Solution {
  insert(root, n) {
    if (root === null) {
      return new TreeNode(n);
    }

    if (n < root.data) {
      root.left = this.insert(root.left, n);
    } else if (n > root.data) {
      root.right = this.insert(root.right, n);
    }

    return root;
  }
}

TypeScript

class Solution {
  insert(root: TreeNode | null, n: number): TreeNode | null {
    if (root === null) {
      return new TreeNode(n);
    }

    if (n < root.data) {
      root.left = this.insert(root.left, n);
    } else if (n > root.data) {
      root.right = this.insert(root.right, n);
    }

    return root;
  }
}

C++

class Solution {
public:
  TreeNode *insert(TreeNode *root, int n) {
    if (root == nullptr) {
      return new TreeNode(n);
    }

    if (n < root->data) {
      root->left = insert(root->left, n);
    } else if (n > root->data) {
      root->right = insert(root->right, n);
    }

    return root;
  }
};

Go

func (s *Solution) Insert(root *TreeNode, n int) *TreeNode {
    if root == nil {
        return &TreeNode{Data: n}
    }

    if n < root.Data {
        root.Left = s.Insert(root.Left, n)
    } else if n > root.Data {
        root.Right = s.Insert(root.Right, n)
    }

    return root
}

Scala

class Solution {
  def insert(root: TreeNode, n: Int): TreeNode = {
    if (root == null) {
      return TreeNode(n)
    }

    if (n < root.data) {
      root.left = insert(root.left, n)
    } else if (n > root.data) {
      root.right = insert(root.right, n)
    }

    root
  }
}

Kotlin

class Solution {
    fun insert(root: TreeNode?, n: Int): TreeNode? {
        if (root == null) {
            return TreeNode(n)
        }

        if (n < root.data) {
            root.left = insert(root.left, n)
        } else if (n > root.data) {
            root.right = insert(root.right, n)
        }

        return root
    }
}

Swift

class Solution {
    func insert(_ root: TreeNode?, _ n: Int) -> TreeNode? {
        if root == nil {
            return TreeNode(n)
        }

        if n < root!.data {
            root!.left = insert(root!.left, n)
        } else if n > root!.data {
            root!.right = insert(root!.right, n)
        }

        return root
    }
}

Ruby

class Solution
  def insert(root, n)
    if root.nil?
      return TreeNode.new(n)
    end

    if n < root.data
      root.left = insert(root.left, n)
    elsif n > root.data
      root.right = insert(root.right, n)
    end

    root
  end
end

Rust

The Rust version uses Option<Box<TreeNode>> for ownership semantics, with .take() to transfer ownership of child nodes during recursive calls.

impl Solution {
    pub fn insert(&self, root: Option<Box<TreeNode>>, n: i32) -> Option<Box<TreeNode>> {
        if root.is_none() {
            return Some(Box::new(TreeNode::new(n)));
        }

        let mut node = root.unwrap();

        if n < node.data {
            node.left = self.insert(node.left.take(), n);
        } else if n > node.data {
            node.right = self.insert(node.right.take(), n);
        }

        Some(node)
    }
}

C#

public class Solution {
    public TreeNode? insert(TreeNode? root, int n) {
        if (root == null) {
            return new TreeNode(n);
        }

        if (n < root.data) {
            root.left = insert(root.left, n);
        } else if (n > root.data) {
            root.right = insert(root.right, n);
        }

        return root;
    }
}

Dart

class Solution {
  TreeNode? insert(TreeNode? root, int n) {
    if (root == null) {
      return TreeNode(n);
    }

    if (n < root.data) {
      root.left = insert(root.left, n);
    } else if (n > root.data) {
      root.right = insert(root.right, n);
    }

    return root;
  }
}

PHP

class Solution {
    public function insert(?TreeNode $root, int $n): ?TreeNode {
        if ($root === null) {
            return new TreeNode($n);
        }

        if ($n < $root->data) {
            $root->left = $this->insert($root->left, $n);
        } else if ($n > $root->data) {
            $root->right = $this->insert($root->right, $n);
        }

        return $root;
    }
}