# 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