< Back





701. Insert into a Binary Search Tree

We're asked to implement the algorithm to add a node to a binary search tree. We just recursively
call this function until we hit a non-existant node, then root.left or root.right will be the new
node - if the value of the new node is less than root or greater, respectively.

The solution is as follows:


  class Solution:
      def insertIntoBST(self, root: Optional[TreeNode], val: int) -> Optional[TreeNode]:
          if not root:
              return TreeNode(val)

          if val < root.val:
              root.left = self.insertIntoBST(root.left, val)
          else:
              root.right = self.insertIntoBST(root.right, val)

          return root


_ Time Complexity:

  O(n) - We inspect all nodes in the binary search tree.

_ Space Complexity:

  O(n) - Our call stack can grow as large as the number of nodes in the binary search tree.