Lintcode 85. Insert Node in a Binary Search Tree

Description:

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

Thinking:

Binary search insertion is a basic operation in the BST.

Step:

1. check whether input is valid.
2. Decide to use recursion/iterasion. Obviously, we use recursion to solve this problem. Since we are doing the same thing again and again.
3. Do we need to create helper function? No, the return value TreeNode is total enough for the recursion.
4. How to do the recursion. By comparing the node.val and root.val. And decide which side we should go. And call Fun(root.left/right, node).
5. Determin the return condition. if root == null then return node. we don't need to think about root.left == null and root.right == null, since the return == null can totally handle this situation.

Code:

/**
 * 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 {

    public TreeNode insertNode(TreeNode root, TreeNode node) {
        // write your code here
        if(root == null) return node;
        if(root.val <= node.val){
           root.right =  insertNode(root.right, node);
        }
        else{
            root.left = insertNode(root.left, node);
        }
        return root;
    }
}

Conclusion:

Important basic operation in BST that we should understand and proficient in.