Problem editorial

Insert into a Binary Search Tree

MediumTree Traversal Patterns (DFS & BFS)Binary Search TreeBinary TreeTree

Insert into a Binary Search Tree: the approach in brief

The problem

A binary search tree (BST) is a binary tree in which every value in a node's left subtree is smaller than the node's value, and every value in its right subtree is larger. Each node may have zero, one, or two children. The root parameter is the root of the existing BST, represented in the input as a level-order array; null denotes a missing child.

Pattern

Insert into a Binary Search Tree is a Tree Traversal Patterns (DFS & BFS) problem, in the Recursive Preorder Traversal subpattern. The pattern covers preorder, inorder, level order traversal, LCA, and serialization

Approach outline

Compare `val` with the current node's value to determine which subtree can contain it.
Continue following left or right child references until the required child position is empty.
When that position is found, attach a new node containing `val` there.

Complexity

The reference solution runs in O(h), where h is the height of the tree. time and O(h) for the recursion stack. space.

The full editorial is part of Pro

It explains the core insight, the complexity analysis and the common mistakes, with a worked solution.

Unlock the full editorial with Pro Solve it first, free

Practise Insert into a Binary Search Tree and the problems around it

Insert into a Binary Search Tree is a Tree Traversal Patterns (DFS & BFS) problem, in the Recursive Preorder Traversal subpattern. Once the approach above makes sense, write it yourself and then work through the neighbouring problems that reuse it.

Insert into a Binary Search Tree