How to insert a node in a binary search tree

Given a binary search tree and an integer, insert this value into the binary search tree and return the root node.

Example

Input:        3   value = 1
             / \  
            2   8 

Output:       3
             / \ 
            2   8
           /
          1

A Binary Search Tree (BST) is a binary tree where each node has a key and meet the following requirements:

• The left subtree of a node contains nodes with keys smaller then the node's key
• The right subtree of a node contains nodes with keys larger then the node's key
• The left and right subtrees are binary search trees

Algorithm

 

 

The insertion should not break the binary search tree. To find a place where to insert a new key, we traverse the binary search tree from root to leaf.

During the traversal, we compare the new value with the node value and:

• if the new key is greater the node value we go to the right
• if the new key is less the node value we go to the left
• if the node is null we insert the new node

here's the step by step example

 

 

Code

    public TreeNode Insert(TreeNode root, int value)
    {
        if (root == null)
        {
            return new TreeNode(value);
        }

        if (root.Value > value)
        {
            root.Left = Insert(root.Left, value);
        }
        else
        {
            root.Right = Insert(root.Right, value);
        }

        return root;
    }

Time complexity : O(h) where h is height of given binary search tree