This post is part of the Algorithms Problem Solving series.
Problem description
This is the Insert Into Binary Search Tree problem. The description looks like this:
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.
Examples
Given the tree:
4
/ \
2 7
/ \
1 3
And the value to insert: 5
The return BST could be
4
/ \
2 7
/ \ /
1 3 5
Solution
The algorithm idea is to traverse the Binary Search Tree and when the current doesn't have the child, we insert the new node there.
As this tree is a BST, we want to traverse it by verifying the if the value we want to insert is greater or smaller than the current node's value.
If it is greater, go to the right side of the tree. If it smaller, go to the left side. If the current node is None, or in other words, the last tree node didn't have the child, we just return a new tree with the value to insert in the appropriate child.
def insert_into_BST(root, val):
if root is None:
return TreeNode(val)
if val < root.val:
root.left = insert_into_BST(root.left, val)
if val > root.val:
root.right = insert_into_BST(root.right, val)
return root