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 def __init__(self, val=0, left=None, right=None):
3 self.val = val
4 self.left = left
5 self.right = right
6
7class Solution:
8 def insertIntoBST(self, root: TreeNode, val: int) -> TreeNode:
9 node = TreeNode(val)
10 if not root:
11 return node
12 current = root
13 while True:
14 if val < current.val:
15 if current.left is None:
16 current.left = node
17 break
18 else:
19 current = current.left
20 else:
21 if current.right is None:
22 current.right = node
23 break
24 else:
25 current = current.right
26 return rootThe Python solution defines a new node and uses a loop to decide whether to traverse left or right. Upon finding the correct spot, it attaches the new node ensuring the BST properties.
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
This recursive solution calls itself for the relevant subtree until a leaf node is found where the new node fits, maintaining BST properties at each recursive step.