Insert Node in 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.

分析：

这个题目告诉我们一个道理：

BST的插入操作总是可以发生在leaf结点的。也就是说，root的left或者right == NULL
的情况。所以遍历二叉树，找到这个NULL，然后插入就可以。

解法：

class Solution {
public:
    /**
     * @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.
     */
    TreeNode* insertNode(TreeNode* root, TreeNode* node) {
        // write your code here
        if (root == NULL) {
            return node;
        }

        TreeNode* prev = NULL;
        TreeNode* curr = root;
        while (curr != NULL) {
            prev = curr;
            if (node->val < curr->val) {
                curr = curr->left;
            } else {
                curr = curr->right;
            }
        }

        if (node->val < prev->val) {
            prev->left = node;
        } else {
            prev->right = node;
        }

        return root;
    }
};