Insert into a Binary Search Tree
Insert a new value into a binary search tree while preserving its ordering property.
Given the root of a binary search tree (BST) and a value val to insert into the tree, insert the value and return the root of the resulting tree.
There can be several valid BSTs that contain the inserted value, but you should perform a standard BST insertion: starting at the root, walk downward -- moving left whenever val is less than the current node's value, and right whenever it's greater -- until you reach an empty spot, and place the new node there. Do not rebalance or otherwise restructure the tree.
Example 1
Input: root = [5,3,8,2,4,7,9], val = 6
Output: [5,3,8,2,4,7,9,null,null,null,null,6]
Explanation: Starting at 5: 6 > 5 so go right to 8; 6 < 8 so go left to 7; 6 < 7 and 7 has no left child, so the new node becomes 7's left child.
Example 2
Input: root = [], val = 5
Output: [5]
Explanation: Inserting into an empty tree makes the new node the root.
Example 3
Input: root = [5], val = 3
Output: [5,3]
Explanation: 3 < 5, and 5 has no left child, so the new node becomes 5's left child.
Constraints
- The number of nodes in the tree is in the range [0, 10000].
- -100000 <= Node.val <= 100000
- -100000 <= val <= 100000
- root is guaranteed to be a valid binary search tree.
- val is guaranteed not to already exist in the tree, so all node values remain unique after insertion.
Follow-up
Can you write both an iterative and a recursive version?
Hints
Companies
No companies reported yet.
Discussion
Sign in to join the discussion.
Loading discussion...
Test results
No test cases yet.