All problems

Insert into a Binary Search Tree

Medium · tree dfs

You are given the root of a binary search tree (BST) and an integer val that is not yet in the tree. In a BST, every value in a node's left subtree is smaller than the node's own value, every value in its right subtree is larger, and no value appears twice.

Add a new node holding val so that the tree is still a BST. The new node must be added as a leaf: every node that is already in the tree stays exactly where it is, with the same parent and the same children, except that one empty child slot now holds the new node. With that rule there is only one possible result.

Return the root of the resulting tree. If the tree is empty, the result is a tree with the single node val.

Examples

Example 1

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

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

5 is larger than 4, so it goes to the right, and smaller than 7, so it 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]

25 is smaller than 40, larger than 20 and smaller than 30, so it becomes the left child of 30.

Example 3

Input: root = [], val = 3

Output: [3]

Constraints

• The number of nodes is in the range [0, 5000], and the height of the tree is at most 900.
• -10^4 <= Node.val <= 10^4, and all values are distinct.
• The tree is a valid binary search tree.
• -10^4 <= val <= 10^4, and val is not already in the tree.