Full lesson preview

Insert into a BST

Insert a value into a Binary Search Tree and return the (possibly new) root.

Python practice15 minTrees & Binary TreesIntermediateLast updated March 29, 2026

Problem statement

Given the root of a Binary Search Tree (BST) and a value to insert, insert the value into the BST and return the root node of the BST after the insertion. It is guaranteed that the new value does not exist in the original BST. The tree should remain a valid BST after insertion. You may return the original root if it is not changed or the new root if the tree was empty.

Task

Write a function to insert a given value into a BST while preserving BST properties.

Examples

Insert into non-empty tree

Input

root = TreeNode(4, TreeNode(2, TreeNode(1), TreeNode(3)), TreeNode(7)); val = 5

Output

After insertion, node with value 5 is placed as left child of 7 (root.right.left.val == 5).

5 > 4 so go right to 7; 5 < 7 so inserted as left child of 7.

Input format

Two arguments: root (TreeNode or None) and val (int).

Output format

Return the root node of the BST after insertion (TreeNode).

Constraints

Number of nodes is in [0, 10^4]. Values are integers. The value to insert does not exist in the tree. Expected average time O(h) where h is tree height, and O(1) extra space for iterative solution.

Samples

Sample 1

Input

root = None; val = 5

Output

A single node tree with value 5 (root.val == 5).

Inserting into an empty tree creates a new node as root.