Sponsored
Sponsored
In this approach, we start from the root and traverse the tree to find an appropriate place for the new node without recursion. At each step, we decide to move left or right depending on the value of the node compared to the value we want to insert. Once we find a suitable spot, we insert the new node as a leaf and return.
Time Complexity: O(h) where h is the height of the tree. Space Complexity: O(1) since no extra space is utilized.
1#include <stdio.h>
2#include <stdlib.h>
3
4struct TreeNode {
5 int val;
6 struct TreeNode *left;
7 struct TreeNode *right;
8};
9
10struct TreeNode* createNode(int val) {
11 struct TreeNode* node = (struct TreeNode*)malloc(sizeof(struct TreeNode));
12 node->val = val;
13 node->left = NULL;
14 node->right = NULL;
15 return node;
16}
17
18struct TreeNode* insertIntoBST(struct TreeNode* root, int val) {
19 struct TreeNode* node = createNode(val);
20 if (root == NULL) return node;
21 struct TreeNode *curr = root, *parent = NULL;
22 while (curr != NULL) {
23 parent = curr;
24 if (val < curr->val)
25 curr = curr->left;
26 else
27 curr = curr->right;
28 }
29 if (val < parent->val)
30 parent->left = node;
31 else
32 parent->right = node;
33 return root;
34}This code creates a new tree node with the given value and traverses the tree starting from the root to find the correct insertion point. It uses a loop to move left or right in the tree and finally attaches the new node as a leaf.
In the recursive method, we start at the root and recursively call the function for either the left or right subtree, based on comparisons, until an appropriate leaf is found for insertion. This method utilizes the call stack to keep track of previous nodes.
Time Complexity: O(h), where h is the height of the tree.
Space Complexity: O(h), due to the recursive stack space.
1class
This recursive Java solution effectively traverses the BST by comparing node values to position the new node appropriately within the binary search tree properties.