NO CODING NO LIFE: Lintcode: 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.

Have you met this question in a real interview?

Yes

Example

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

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

Challenge

Can you do it without recursion?

Tags Expand

LintCode Copyright Binary Search Tree

Codes Reference:
http://yuanbin.gitbooks.io/algorithm/content/zh-cn/binary_search_tree/insert_node_in_a_binary_search_tree.html

Recursive Solution:
Time: average: O(log n) best O(1) worst O(n)
Stack Space: O(L) -- best: O(1) worst:O(n)

/**
 * Definition of TreeNode:
 * class TreeNode {
 * public:
 *     int val;
 *     TreeNode *left, *right;
 *     TreeNode(int val) {
 *         this->val = val;
 *         this->left = this->right = 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;
        if(node->val <= root->val) root->left = insertNode(root->left, node);
        else root->right = insertNode(root->right, node);
        return root;
    }
};

Iterative Solution:

Time: O(logn)

Space: O(1)

/**
 * Definition of TreeNode:
 * class TreeNode {
 * public:
 *     int val;
 *     TreeNode *left, *right;
 *     TreeNode(int val) {
 *         this->val = val;
 *         this->left = this->right = 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* cur = root;
        while(1){
            TreeNode* prev = cur;
            if(node->val <= cur->val) {
                if(cur->left == NULL) {
                    cur->left = node;
                    break;}
                else cur = cur->left;
            }
            else{
                if(cur->right == NULL) {
                    cur->right = node;
                    break;}
                else cur = cur->right;
            }
        }
        return root;
    }
};

Note: break in Line 29 and Line 35 can be replaced by return root

NO CODING NO LIFE

2015年9月9日星期三

Lintcode: Insert Node in a Binary Search Tree

没有评论:

发表评论