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.
1public class TreeNode {
2 public int val;
3 public TreeNode left;
4 public TreeNode right;
5 public TreeNode(int x) { val = x; }
6}
7
8public class Solution {
9 public TreeNode InsertIntoBST(TreeNode root, int val) {
10 TreeNode node = new TreeNode(val);
11 if (root == null) return node;
12 TreeNode curr = root;
13 while (true) {
14 if (val < curr.val) {
15 if (curr.left == null) {
16 curr.left = node;
17 break;
18 }
19 curr = curr.left;
20 } else {
21 if (curr.right == null) {
22 curr.right = node;
23 break;
24 }
25 curr = curr.right;
26 }
27 }
28 return root;
29 }
30}This C# solution implements the insertion into a BST without recursion. A loop is used to descend through the tree based on the comparison until the new node can be appended 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.
1using namespace std;
struct TreeNode {
int val;
TreeNode *left, *right;
TreeNode(int x) : val(x), left(nullptr), right(nullptr) {}
};
TreeNode* insertIntoBST(TreeNode* root, int val) {
if (!root) return new TreeNode(val);
if (val < root->val)
root->left = insertIntoBST(root->left, val);
else
root->right = insertIntoBST(root->right, val);
return root;
}In this C++ recursive solution, the function inserts a new node into the tree by exploring either the left or right subtrees based on comparisons until a suitable spot is found.