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

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

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

推荐阅读:
已知半圆周长如何求半径  0.19385÷29的商是循环小数吗  已知圆面积求阴影部分的面积  整个路程是多少km  箕子碑原文及翻译  桐叶封弟辨原文及翻译  驳复仇议原文及翻译  柳子厚墓志铭原文及翻译  祭鳄鱼文原文及翻译  《古文观止》中十大经典金句—人生的行动指南 
评论列表
添加评论