Implement a method to insert a node into a Binary Search Tree. Return the root of the modified tree.

**Example:**

4 4

/ \ / \

2 8 insert(6)=> 2 8

/ \ / \

5 10 5 10

\

6

Need a **hand?** Try out these hints, one at a time.

Use the data property of a binary search tree.

1. If the root is

2. Else if the input data is less than the data in the root node, recurse through the left sub tree,

3. Else if the input data is greater than the data in the root node, recurse through the right sub tree,

4. Return

`null`

, create a new node with the input data and return that node.2. Else if the input data is less than the data in the root node, recurse through the left sub tree,

`root.left = insert(root.left, data);`

3. Else if the input data is greater than the data in the root node, recurse through the right sub tree,

`root.right = insert(root.right, data);`

4. Return

`root`

.
public TreeNode insert(TreeNode root, int data) { }

**C**

**Java**

**Python**