Insert into a Binary Search Tree

Given the root of a binary search tree and a value, insert the value into the BST and return the root of the updated tree. Pattern focus: BST Insert and Delete. Insert by comparing the value with each node and moving down the unique path where it belongs.

Input Format

root = binary tree root, val = value to insert

Output Format

updated BST root

Constraints

  • 0 <= number of nodes <= 10^5
  • -10^9 <= node values <= 10^9
  • root and val must satisfy the format described in inputFormat.

Examples

Example 1:

Input:

root = [4,2,7,1,3]
val = 5

Output:

[4,2,7,1,3,5]

Explanation:

Value 5 becomes the left child of 7.

Example 2:

Input:

root = [40,20,60,10,30,50,70]
val = 25

Output:

[40,20,60,10,30,50,70,null,null,25]

Explanation:

Value 25 is inserted as the left child of 30.

Loading...
Insert into a Binary Search Tree