Insert into a Binary Search Tree | LeetCode 701 | Python | Solution

Click here to see the problem details. Read the problem details first.

Concept

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.

For 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.

Coding Part

Iterative Solution

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

Recursive Solution

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

Last Words

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.