Leetcode 0701. Insert into a Binary Search Tree

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

What we need to do in this problem is just traverse our tree and find the correct place for our new value:

1. If we have val < root.val, we need to go left: if it is possible, we go left; if left children is not existing, then we create it with val value.
2. If we have val > root.val, we need to go right: if it is possible, we go right; if right children is not existing, then we create it with val value.

Finally, we run our dfs function from root and return root.

Complexity time and space complexity is O(h), where h is height of our tree.

class Solution:
    def insertIntoBST(self, root, val):
        def dfs(root):
            if val < root.val:
                if root.left:
                    dfs(root.left)
                else:
                    root.left = TreeNode(val)
            else:
                if root.right:
                    dfs(root.right)
                else:
                    root.right = TreeNode(val)
        
        if not root: return TreeNode(val)
        dfs(root)
        return root

If you like the solution, you can upvote it on leetcode discussion section: Problem 0701