Click here to see the problem details. Read the problem details first.
This is clearly a Tree related problem and a medium-type problem. In my sense, it’s not that difficult if you have a basic concept about BST (Binary Search Tree). BST is also a Binary Tree.
So what is a Binary Search Tree? BST is a type of Binary Tree, where the left subtree of a node contains equal or smaller values, and the right subtree contains equal or greater values. BST is also known as sorted Tree.
In this problem, we will be given a root node of a BST and a value to insert into the tree by maintaining the BST rules. After that, we will return the root node of the given tree.
To solve this problem, we have to search for a valid place for the given value. For that, we have to traverse through the tree. if
val < node.val, then we will go to the left. Before going to the left, we will check that if there is no left child, create a TreeNode with the given value in that place. And our job is done.
val > node.val, we will do the exact opposite thing.
We can solve this problem in many ways using the iterative method or recursive method.
class Solution: def insertIntoBST(self, root: TreeNode, val: int) -> TreeNode: if root is None: return TreeNode(val) current = root while current: if val < current.val: if current.left is None: current.left = TreeNode(val) break current = current.left else: if current.right is None: current.right = TreeNode(val) break current = current.right return root
class Solution: def insertIntoBST(self, root: TreeNode, val: int) -> TreeNode: if root is None: return TreeNode(val) if val < root.val: root.left = self.insertIntoBST(root.left, val) else: root.right = self.insertIntoBST(root.right, val) return root
If you submit these codes on LeetCode, these got accepted. But you should never submit any code if you don’t understand the solution.
So I hope this gives you a bit of an idea of this problem solution.