Teaching Kids Programming – Insert a Node into a Binary Search Tree via Recursion

Teaching Kids Programming: Videos on Data Structures and Algorithms

Given the root node of a binary search tree (BST) and a value to be inserted into the tree, insert the value into the BST. Return the root node of the BST after the insertion. It is guaranteed that the new value does not exist in the original BST.

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

For example,

Given the tree:

        4
       / \
      2   7
     / \
    1   3

And the value to insert: 5
You can return this binary search tree:

         4
       /   \
      2     7
     / \   /
    1   3 5

This tree is also valid:

         5
       /   \
      2     7
     / \   
    1   3
         \
          4

Recursive Algorithm to Insert a Node into BST

If current node is None, we create a node and return it. If it is larger than the current node, we need to insert the node somewhere in the right tree, otherwise we need to insert it somewhere in the left tree.

We can recursively walk through the BST until we find a proper place to insert it.

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15

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

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

The time complexity is O(H) and the space complexity is also O(H) where H is the height of the BST which is O(logN) if it is a highly balanced Binary Search Tree.

See other implementations of Inserting into BST:

• Teaching Kids Programming – Insert a Node into a Binary Search Tree via Recursion
• How to Insert into a Binary Search Tree (Recursive and Iterative)?
• GoLang: Insert into a Binary Search Tree via Recursion

–EOF (The Ultimate Computing & Technology Blog) —