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.
1class TreeNode {
2 constructor(val, left = null, right = null) {
3 this.val = val;
4 this.left = left;
5 this.right = right;
6 }
7}
8
9function insertIntoBST(root, val) {
10 const node = new TreeNode(val);
11 if (root === null) return node;
12
13 let current = root;
14 while (true) {
15 if (val < current.val) {
16 if (current.left === null) {
17 current.left = node;
18 break;
19 }
20 current = current.left;
21 } else {
22 if (current.right === null) {
23 current.right = node;
24 break;
25 }
26 current = current.right;
27 }
28 }
29 return root;
30}This JavaScript approach uses a simple while loop to traverse the tree, comparing the node values to find an appropriate spot for the new node. On reaching the correct position, the new node is appended.
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.
1
In Python, the recursive solution explores sub-trees by comparing values at each node, inserting the new node at its correct position, and maintaining BST properties.