You are given the root node of a binary search tree (BST) and a value to insert into the tree. Return the root node of the BST after the insertion. It is guaranteed that the new value does not exist in the original BST.
Notice that there may exist multiple valid ways for the insertion, as long as the tree remains a BST after insertion. You can return any of them.
Example 1:
Input: root = [4,2,7,1,3], val = 5
Output: [4,2,7,1,3,5]
Explanation: Another accepted tree is:
Example 2:
Input: root = [40,20,60,10,30,50,70], val = 25
Output: [40,20,60,10,30,50,70,null,null,25]
Example 3:
Input: root = [4,2,7,1,3,null,null,null,null,null,null], val = 5
Output: [4,2,7,1,3,5]
Constraints:
The number of nodes in the tree will be in the range [0, 104].
-108 <= Node.val <= 108
All the values Node.val are unique.
-108 <= val <= 108
It's guaranteed that val does not exist in the original BST.
Solutions
Solution 1: Recursion
If the root node is null, we directly create a new node with the value $\textit{val}$ and return it.
If the root node's value is greater than $\textit{val}$, we recursively insert $\textit{val}$ into the left subtree and update the root of the left subtree with the returned root node.
If the root node's value is less than $\textit{val}$, we recursively insert $\textit{val}$ into the right subtree and update the root of the right subtree with the returned root node.
The time complexity is $O(n)$, and the space complexity is $O(n)$. Here, $n$ is the number of nodes in the binary tree.
1 2 3 4 5 6 7 8 9101112131415
# Definition for a binary tree node.# class TreeNode:# def __init__(self, val=0, left=None, right=None):# self.val = val# self.left = left# self.right = rightclassSolution:definsertIntoBST(self,root:Optional[TreeNode],val:int)->Optional[TreeNode]:ifrootisNone:returnTreeNode(val)ifroot.val>val:root.left=self.insertIntoBST(root.left,val)else:root.right=self.insertIntoBST(root.right,val)returnroot
/** * Definition for a binary tree node. * type TreeNode struct { * Val int * Left *TreeNode * Right *TreeNode * } */funcinsertIntoBST(root*TreeNode,valint)*TreeNode{ifroot==nil{return&TreeNode{Val:val}}ifroot.Val>val{root.Left=insertIntoBST(root.Left,val)}else{root.Right=insertIntoBST(root.Right,val)}returnroot}