How to Insert into a Binary Search Tree (Recursive and Iterative

  • 时间:2020-10-12 15:56:23
  • 分类:网络文摘
  • 阅读:155 次

Given the root node of a binary search tree (BST) and a value to be inserted into the tree, insert the value into the BST. Return the root node of the BST after the insertion. It is guaranteed that the new value does not exist in the original BST.

Note that there may exist multiple valid ways for the insertion, as long as the tree remains a BST after insertion. You can return any of them.

For example,

Given the tree:

        4
       / \
      2   7
     / \
    1   3

And the value to insert: 5
You can return this binary search tree:

         4
       /   \
      2     7
     / \   /
    1   3 5

This tree is also valid:

         5
       /   \
      2     7
     / \   
    1   3
         \
          4

A BST (Binary Search Tree) is a binary tree that the left nodes are always smaller/equal than the parent nodes and the right nodes are bigger. To insert into a BST, we can always use two approaches to walk through the tree until the leaves.

Recursion

If the tree is NULL, we simply return a new node with the target value to insert. On other cases, we can recursively re-assign the left or right tree pointer of the root, depending on the target value – either left tree if the target value is smaller than the root, or right tree if it is strictly bigger than the root value.

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
/**
 * Definition for a binary tree node.
 * struct TreeNode {
 *     int val;
 *     TreeNode *left;
 *     TreeNode *right;
 *     TreeNode(int x) : val(x), left(NULL), right(NULL) {}
 * };
 */
class Solution {
public:
    TreeNode* insertIntoBST(TreeNode* root, int val) {
        if (root == NULL) return new TreeNode(val);
        if (val < root->val) root->left = insertIntoBST(root->left, val);
        if (val > root->val) root->right = insertIntoBST(root->right, val);
        return root;
    }
};
/**
 * Definition for a binary tree node.
 * struct TreeNode {
 *     int val;
 *     TreeNode *left;
 *     TreeNode *right;
 *     TreeNode(int x) : val(x), left(NULL), right(NULL) {}
 * };
 */
class Solution {
public:
    TreeNode* insertIntoBST(TreeNode* root, int val) {
        if (root == NULL) return new TreeNode(val);
        if (val < root->val) root->left = insertIntoBST(root->left, val);
        if (val > root->val) root->right = insertIntoBST(root->right, val);
        return root;
    }
};

The runtime complexity is O(N) i.e. in worst cases, when the tree is degraded into single-linked list, N nodes need to be visited before new node is insert into the end. Same goes for space complexity where O(N) – N is the depth of the stack.

Iteration

The above idea can be implemented iteratively where the parent node pointer is recorded. We walk to the leave and insert the new node to the parent pointer.

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
34
35
/**
 * Definition for a binary tree node.
 * struct TreeNode {
 *     int val;
 *     TreeNode *left;
 *     TreeNode *right;
 *     TreeNode(int x) : val(x), left(NULL), right(NULL) {}
 * };
 */
class Solution {
public:
    TreeNode* insertIntoBST(TreeNode* root, int val) {
        if (root == NULL) {
            TreeNode* newNode = new TreeNode(val);
            return newNode;
        }
        TreeNode* x = root;
        TreeNode* p;
        while (x != NULL) {
            p = x;
            if (val <= x->val) {
                x = x->left;
            } else {
                x = x->right;
            }
        }
        TreeNode* node = new TreeNode(val);
        if (val <= p->val) {
            p->left = node;
        } else {
            p->right = node;
        }
        return root;
    }
};
/**
 * Definition for a binary tree node.
 * struct TreeNode {
 *     int val;
 *     TreeNode *left;
 *     TreeNode *right;
 *     TreeNode(int x) : val(x), left(NULL), right(NULL) {}
 * };
 */
class Solution {
public:
    TreeNode* insertIntoBST(TreeNode* root, int val) {
        if (root == NULL) {
            TreeNode* newNode = new TreeNode(val);
            return newNode;
        }
        TreeNode* x = root;
        TreeNode* p;
        while (x != NULL) {
            p = x;
            if (val <= x->val) {
                x = x->left;
            } else {
                x = x->right;
            }
        }
        TreeNode* node = new TreeNode(val);
        if (val <= p->val) {
            p->left = node;
        } else {
            p->right = node;
        }
        return root;
    }
};

–EOF (The Ultimate Computing & Technology Blog) —

推荐阅读:
生容易,活容易,生活真的不容易!  太精无路,太苛无友  人这一生,最无情的不是人,而是…  最好的爱,从来都不只是爱  最好的感情,是什么  后悔药,你要吗?  无法重来的一生!  笑看人生,让抱怨随风而逝 !  人生有五个怕,你最怕哪一个?  老实人,为什么不吃香?(超现实) 
评论列表
添加评论