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

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

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) —

推荐阅读:
这艘轮船最多驶出多远就应返回  两个完全相同的长方体恰好拼成一个正方体  从右往左数,小兰排在第几个?  网站安全公司对个人隐私保护措施  网站渗透测试行业中需要文凭吗  友情链接:对网站排名作用都深入了解吗?  灵魂拷问自己:SEO是什么?疫情对SEO有什么影响?  案例分析:做谷歌SEO怎么选择更好的友情链接  404是什么意思?404错误页面是怎么造成的  Google SEO怎么用外链优化来增加网站权重 
评论列表
添加评论