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