Practice/LinkedIn/Leetcode 701. Insert into a Binary Search Tree

Leetcode 701. Insert into a Binary Search Tree

CodingOptional

Problem

You are given the root node of a binary search tree (BST) and an integer value that needs to be added to the tree. The value is guaranteed to not already exist in the BST. Your task is to insert this new value into the tree while maintaining the binary search tree property, then return the root of the modified tree.

A binary search tree has the property that for every node, all values in its left subtree are smaller than the node's value, and all values in its right subtree are greater than the node's value.

You may insert the new node anywhere in the tree as long as the BST property is maintained. The most common approach is to insert it as a new leaf node.

Requirements

1. Insert the given value into the BST at an appropriate position
2. Maintain the binary search tree property after insertion
3. Return the root of the modified tree
4. The value to insert is guaranteed to not already exist in the tree

Constraints

• The number of nodes in the tree will be in the range [0, 10^4]
• -10^8 ≤= Node.val ≤= 10^8
• All values in the BST are unique
• -10^8 ≤= val ≤= 10^8
• The value val does not exist in the original BST

Examples

Example 1:

` Input: root = [4,2,7,1,3], val = 5 Output: [4,2,7,1,3,5] Explanation: The original tree: 4 /
2 7 /
1 3

After inserting 5, we traverse: 4 -> 7 (go left because 5 < 7) The result: 4 /
2 7 / \ / 1 3 5 `

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: Starting at 40, go left to 20, then right to 30, then left to insert 25

Example 3:

Input: root = [], val = 5 Output: [5] Explanation: The tree is empty, so the new value becomes the root