Search / Insert into BST
You are given the root of a Binary Search Tree (BST) and an integer key.
- If the key already exists in the BST, return the node containing the key.
- Otherwise, insert the key into the BST while maintaining its properties and return the root of the updated tree.
A Binary Search Tree (BST) follows these rules:
- All values in the left subtree are smaller than the node's value.
- All values in the right subtree are greater than the node's value.
- Both left and right subtrees are also BSTs.
Examples
Input: root = [4,2,7,1,3], key = 2
Output: [4,2,7,1,3]
Explanation: The key already exists in the BST, so the tree remains unchanged.
Input: root = [4,2,7,1,3], key = 5
Output: [4,2,7,1,3,5]
Explanation: The key 5 is inserted while maintaining the BST property.
Input: root = [], key = 8
Output: [8]
Explanation: Since the BST is empty, the new node becomes the root.
Constraints
- 0 = Number of nodes = 105
- -10? = Node.data, key = 10?
Companies
Topics
Solution.cs C#JavaPythonC++Javascript
Unlock the code editor
Sign in to write, run, and submit your solution against the full test suite.
- Run code against sample & hidden test cases
- Save submissions and track your streak
- Compare with editorial & community solutions