Insert Node in Binary Search Tree

I always forget to practice the updating operations. Here to pick it up.

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.

Example

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

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

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33

/** * Definition of TreeNode: * public class TreeNode { * public int val; * public TreeNode left, right; * public TreeNode(int val) { * this.val = val; * this.left = this.right = null; * } * } */ public class Solution { /** * @param root: The root of the binary search tree. * @param node: insert this node into the binary search tree * @return: The root of the new binary search tree. */ public TreeNode insertNode(TreeNode root, TreeNode node) { // write your code here if (root == null) { return node;//key } if (root.val > node.val) { //insert to left tree //returned node is either original link or new node to link to! root.left = insertNode(root.left, node); } else { //else insert to right tree root.right = insertNode(root.right, node); } return root;//key } }