Description

701. Insert into a Binary Search Tree

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

Notice 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.

Example 1:

Input: root = [4,2,7,1,3], val = 5
Output: [4,2,7,1,3,5]
Explanation: Another accepted tree is:

Example 2:

Input: root = [40,20,60,10,30,50,70], val = 25
Output: [40,20,60,10,30,50,70,null,null,25]
Example 3:

Input: root = [4,2,7,1,3,null,null,null,null,null,null], val = 5
Output: [4,2,7,1,3,5]

Constraints:

The number of nodes in the tree will be in the range [0, 10^4].
-10^8 <= Node.val <= 10^8
All the values Node.val are unique.
-10^8 <= val <= 10^8
It's guaranteed that val does not exist in the original BST.

Answer & Explaining

#include <stdio.h>
#include <stdlib.h>

//插入一個新節點到BST中
struct TreeNode* insertIntoBST(struct TreeNode* root, int val) {
    // 如果當前節點為空，創建一個新節點
    if (root == NULL) {
        struct TreeNode* newNode = (struct TreeNode*)malloc(sizeof(struct TreeNode)); //分配記憶體
        newNode->val = val;
        newNode->left = NULL; //左節點為空
        newNode->right = NULL; //右節點為空
        return newNode;
    }
    
    // 根據 val 值決定插入到左子樹還是右子樹
    if (val < root->val) { //如果值小於root，往left subtree
        root->left = insertIntoBST(root->left, val); // 遞迴到左子樹
    } else { //值大於root，往right subtree
        root->right = insertIntoBST(root->right, val); // 遞迴到右子樹
    }
    
    return root; // 返回root
}

// 輔助函數，創建新節點
struct TreeNode* createNode(int val) {
    struct TreeNode* node = (struct TreeNode*)malloc(sizeof(struct TreeNode));
    node->val = val;
    node->left = NULL;
    node->right = NULL;
    return node;
}

Testing

#include <stdio.h>
#include <stdlib.h>

//定義binary tree node
struct TreeNode {
    int val;
    struct TreeNode *left;
    struct TreeNode *right;
};

//插入一個新節點到BST中
struct TreeNode* insertIntoBST(struct TreeNode* root, int val) {
    // 如果當前節點為空，創建一個新節點
    if (root == NULL) {
        struct TreeNode* newNode = (struct TreeNode*)malloc(sizeof(struct TreeNode)); //分配記憶體
        newNode->val = val;
        newNode->left = NULL; //左節點為空
        newNode->right = NULL; //右節點為空
        return newNode;
    }
    
    // 根據 val 值決定插入到左子樹還是右子樹
    if (val < root->val) { //如果值小於root，往left subtree
        root->left = insertIntoBST(root->left, val); // 遞迴到左子樹
    } else { //值大於root，往right subtree
        root->right = insertIntoBST(root->right, val); // 遞迴到右子樹
    }
    
    return root; // 返回root
}

// 輔助函數，創建新節點
struct TreeNode* createNode(int val) {
    struct TreeNode* node = (struct TreeNode*)malloc(sizeof(struct TreeNode));
    node->val = val;
    node->left = NULL;
    node->right = NULL;
    return node;
}

// 測試函數
void testInsertIntoBST() {
    // 建立測試樹 [4,2,7,1,3]
    struct TreeNode* root = createNode(4);
    root->left = createNode(2);
    root->right = createNode(7);
    root->left->left = createNode(1);
    root->left->right = createNode(3);

    // 插入 5
    root = insertIntoBST(root, 5);

    // 打印插入後樹的結果（這裡僅簡單地打印根節點和其左右子樹的值）
    printf("Root: %d\n", root->val);
    printf("Left Child: %d\n", root->left->val);
    printf("Right Child: %d\n", root->right->val);
    printf("New Node (should be 5 in right subtree): %d\n", root->right->left->val);
}

// 主測試函數
int main() {
    testInsertIntoBST();
    return 0;
}