Insert Node in a Binary Search Tree

Given a binary search tree and a new tree node, insert the node into the tree. You should keep the tree still be a valid binary search tree.

Notice

You can assume there is no duplicate values in this tree + node.

Example Given binary search tree as follow, after Insert node 6, the tree should be:

  2             2
 / \           / \
1   4   -->   1   4
   /             / \ 
  3             3   6

Solution: Binary search tree---find the position and insert the new node to the leaf.

public TreeNode insertNode(TreeNode root, TreeNode node) {
    if(root == null) {
        return node;
    }
    TreeNode p = root;
    TreeNode insert = null;
    while(p != null) {
        insert = p;
        if(node.val > p.val) {
            p = p.right;
        }
        else {
            p = p.left;
        }
    }
    if(node.val > insert.val) {
        insert.right = node;
    }
    else {
        insert.left = node;
    }
    return root;
}