DSA Tracker

Medium

Insert into a BST

A medium BST problem included in Love Babbar 450, Striver A2Z. Below: the roles whose interviews prioritise this topic, and how to practise it.

Topic
BST
Sheets
2
Core for
2 roles
Platform
LeetCode
Practice in the compilerWatch this solved step by step

The problem

Given the root of a binary search tree and an integer value, insert a new node with that value into the BST while maintaining the BST property. Return the root of the updated BST.

Example 1

Input
root=[4,2,7,1,3], val=5
Output
[4,2,7,1,3,5]
Why
Value 5 is greater than 4 (go right to 7), less than 7 (go left), and inserted as left child of 7.

Example 2

Input
root=[4,2,7,1,3], val=8
Output
[4,2,7,1,3,null,8]
Why
Value 8 is greater than 4 (go right to 7), greater than 7 (go right), inserted as right child of 7.

Example 3

Input
root=[], val=1
Output
[1]
Why
Inserting into an empty tree creates a new root.

Constraints

  • The number of nodes is in the range [0, 104].
  • -108 <= Node.val <= 108
  • -108 <= val <= 108
  • All values are unique.

How to think about it

Updated 2026-09-09

Every new key in a BST has a unique valid leaf position where search naturally falls off the tree. You never need to rotate or reshape existing subtrees: just navigate left or right until hitting a null reference, and hook the new node there.

Approaches, worst first

  1. Recursive insertion

    time O(h) · space O(h)

    Compare val with root: if smaller, assign `root.left = insert(root.left, val)`; if greater, assign `root.right = insert(root.right, val)`. When root is null, return the fresh node. Simple and clean, but incurs O(h) recursion frames.

  2. Iterative pointer walkWrite this one

    time O(h) · space O(1)

    Follow child links iteratively while tracking the parent. When the current pointer becomes null, attach the new node to the parent's left or right pointer based on value comparison. Avoids recursion and runs in constant extra space.

Where people lose marks · 2
  • Empty tree handling: forgetting that `root == null` requires returning the newly allocated node directly, otherwise dereferencing null throws.
  • Reassigning pointers improperly: updating a local `curr` variable without attaching the new node to `parent.left` or `parent.right` leaves the tree unchanged.

The theory behind it

BST — the ground this problem stands on. All BST problems

What BST is

A binary search tree is a binary tree that enforces a strict ordering rule at every node. Every value stored in a node's left branch must be smaller than the node itself, and every value in its right branch must be larger. Because this rule holds true everywhere down the tree, searching for a value does not require checking every branch. At each step, a single comparison lets you discard an entire half of the remaining nodes.

When to reach for it

Reach for a binary search tree when problems mention sorted tree structures, finding the kth smallest element, checking tree validity, or searching within a range of values. Signals include queries for the next greater element in a dynamic set, finding the lowest common ancestor in a sorted tree, or converting sorted arrays into height-balanced trees. When data must remain sorted while supporting continuous insertions and lookups, BST properties are the target.

How the pattern works

Use the ordering property to prune entire subtrees. When looking for a key, move left if the target is smaller than the current node, or move right if it is larger, stopping when values match or when reaching a null link. For validating a tree, do not merely compare a node to its immediate children; pass valid lower and upper value bounds down through recursive calls. Walking a valid binary search tree in-order visits all values in strictly increasing numerical order.

What each operation costs

OperationTime
search, insert, or delete on balanced treeO(log n)
search, insert, or delete on degenerate line treeO(n)
in-order traversal visiting all nodes in sorted orderO(n)
What usually goes wrong with BST
  • Validating a tree by checking only immediate children against the parent, missing violations where a node deep in the left subtree is larger than an ancestor higher up.
  • Allowing duplicate values on the wrong side when the problem specification requires strictly smaller values on the left and strictly greater on the right.
  • Deleting a node with two children by removing it directly instead of replacing its value with its in-order predecessor or successor and deleting that leaf instead.

Which roles need this problem

BST is a core topic for these 2 roles — if you're targeting one of them, this problem is early in your path, not optional.

SDE / Backend EngineerDatabase Engineer

Secondary for 6 more roles, including Full-Stack Developer, Android Developer, iOS Developer.

Track this in your role's order

Pick your target role and all 370 problems — including this one — resequence to what that interview actually asks. Free.

Start free

More BST problems

Problem set and role mapping as of .