[Leet Code] Insert into a Binary Search Tree

Leetcode: https://leetcode.com/problems/insert-into-a-binary-search-tree/

Problem:

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]

Solution:

# Definition for a binary tree node.
# class TreeNode(object):
#     def __init__(self, val=0, left=None, right=None):
#         self.val = val
#         self.left = left
#         self.right = right
class Solution(object):
    def insertIntoBST(self, root, val):
        """
        :type root: TreeNode
        :type val: int
        :rtype: TreeNode
        """
        if not root:
            return TreeNode(val)
        self.traverse(root, val)
        return root
        
    def traverse(self, root, val):
        if root:
            if val > root.val:
                if root.right:
                    self.traverse(root.right, val)
                else:
                    root.right = TreeNode(val)
            if val < root.val:
                if root.left:
                    self.traverse(root.left, val)
                else:
                    root.left = TreeNode(val)

Explanation:

First we check for the edge case of if the root node is empty, then we will still need to insert the value that we’ve been given, so we return the value in the TreeNode data type. Then we carry on with normal operations, we create a helper method called traverse, and this takes the same parameters as the main method. We check that root is present, then we check if the value we’ve been given (make sure to note that it’s an int, and our nodes are of format TreeNode, so we need to compare on the root.val which is an integer) is greater than or less than the root node’s value. If it’s greater than, we traverse down the right side of the tree. If it’s less than, we traverse down the left side of the tree. Then we check if there is a left or a right node present after that node, and if there is, continue to traverse, however, if not, then we want to insert our “new node” in here.