DEV Community πŸ‘©β€πŸ’»πŸ‘¨β€πŸ’»

Cover image for Algorithms Problem Solving: Insert into Binary Search Tree
TK
TK

Posted on • Originally published at leandrotk.github.io

Algorithms Problem Solving: Insert into Binary Search Tree

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
Enter fullscreen mode Exit fullscreen mode

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
Enter fullscreen mode Exit fullscreen mode

Resources

Top comments (0)

🌚 Browsing with dark mode makes you a better developer by a factor of exactly 40.

It's a scientific fact.