Trees - Insert into a BST

Given the root of a BST and a value to insert, insert the value into the BST and return the root. The new value does not exist in the original BST.

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

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

Recursively traverse the BST. Go left if val < root.val, right if val > root.val. When reaching a null node, create and return a new node.

If root == null: return new TreeNode(val).
If val < root.val: root.left = insert(root.left, val).
Else: root.right = insert(root.right, val).
Return root.

class Solution { public TreeNode insertIntoBST(TreeNode root, int val) { if (root == null) return new TreeNode(val); if (val < root.val) root.left = insertIntoBST(root.left, val); else root.right = insertIntoBST(root.right, val); return root; } }

Time Complexity: O(H)
Space Complexity: O(H)