701. Insert into a Binary Search Tree
Leetcode #: 701
Name: Insert into a Binary Search Tree
Companies asked: Airbnb, Amazon, Meta, Google, LinkedIn, Twitter
You’re given the root node of a Binary Search Tree (BST) and a value to insert into the tree. Your task is to insert a node with the value provided and return the root node of the BST.
It’s also worth to note that the problem guarantees that there won’t be a node in the BST already that has a value of value. This is because it is not common to have duplicates in BSTs just like how it is not possible to have cycles in a binary tree.
The problem also acknowledges that there may be multiple ways in which you can insert a node with the given value as well so all that is being asked is that after your implementation, the inherent sorting property of a BST is maintained.
The easiest or most convenient way to add a node in a BST is to add the node to an existing leaf node. Conversely, it’s not as easy to insert a node, for instance, at the root of a BST if it already has a root. Because the inherent nature of a BST is recursive, I prefer to write my algorithm recursively as opposed to iteratively.
The base case will be a conditional statement checking if the root node is null and if so, instead of returning null like how we did for problem #700 Search in a Binary Search Tree, we’ll be returning a new instance of a TreeNode with its value as the given value. This is because we want to insert the new TreeNode below an existing leaf node.
if not root:
For the main body of our logic, we’ll simply compare the given value against the value of the root node. If the given value happens to be greater than root.val, then we know we want to insert our new node with the given value into the right subtree. Thus, we’ll want to set root.right to be a recursive call of the right subtree with the given value.
if val > root.val:
root.right = insertIntoBST(root.right, val)
Conversely, if the given value happens to be smaller than root.val, then we know we want to insert our new node with the given value into the left subtree. We’ll follow a similar procedure as above by setting our root.left to be a recursive call of the left subtree with the given value.
elif val < root.val:
root.left = insertIntoBST(root.left, val)
Finally, you want to return the root as the last line in the function because the problem is asking for us to return the root node of the BST after the insertion.
Thank you for reading!
In case if you haven’t yet joined my Discord server where I host daily sessions on data structures & algorithms for free, please join via the link shared below.
If you have any questions or comments, please don’t be afraid to connect with me on any of the platforms below or feel free to send me an email at firstname.lastname@example.org