# 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