leetExpert
Practice

Insert into a Binary Search Tree

Module 18 · BST & Ordered Structures

Problem

Given the root of a binary search tree and a value val not already present, insert val into the tree and return the root. Any valid BST that contains all the original values plus val is accepted — there is more than one correct shape, but the standard result is the one where the new value becomes a leaf.

Examples

Example 1

Inputroot = [4,2,7,1,3], val = 5Output[4,2,7,1,3,5]

Explanation. 5 lands as a leaf under 7

Example 2

Inputroot = [], val = 8Output[8]
text
      4                       4
     / \                     / \
    2   7     insert 5      2   7
   / \                     / \  /
  1   3                   1  3 5

Constraints

0 ≤ n ≤ 10⁴ nodes · −10⁸ ≤ values ≤ 10⁸ · val is not already in the tree

Attempt it first

You already derived this operation in concept lesson 1 — this problem is here so you can produce it cold, in both a recursive and an iterative form, and articulate exactly why the spot you land on is the only place the value can go. Before revealing anything: where does a search for val end up in a tree that doesn't contain val, and why is that endpoint automatically a legal insertion point?