Insert Node in BST
Concepts and Basic Operations DSA practice problem on Onlearn.
Difficulty: easy.
Topics: Insert a given Node in Binary Search Tree, Binary Search Tree, Binary Tree, Node, Traversal, Recursion, Iteration, Time Complexity, Space Complexity, iterative algorithms, complexity analysis, binary search tree, recursion, tree traversal.
You are given the root of a Binary Search Tree (BST) and an integer value val. Insert a new node with the val into the BST, maintaining the BST properties. If the tree is empty, the new node becomes the root. It is guaranteed that the value to be inserted is not already present in the BST. A Binary Search Tree (BST) is a data structure where for any node: All values in its left subtree are less than its own value. All values in its right subtree are greater than its own value. Both the left and right subtrees are also BSTs. Input: root: A TreeNode representing the root of the BST. If the tree is empty, root will be null. val: An integer representing the value to be inserted. Output: The TreeNode representing the root of the modified BST after insertion. Constraints: The number of nodes in the tree is in the range [0, 10^4]. 10^9 <= Node.val <= 10^9 10^9 <= val <= 10^9 val will not exist in the BST. Sample Test Cases: Example 1: Input Tree: 4 / \\ 2 7 / \\ 1 3 val = 5 Output Tree: 4 / \\ 2 7 / \\ / 1 3 5 Explanation: The new node with value 5 is inserted as the left child of node 7. Example 2: Input Tree: null val = 10 Output Tree: 10 Explanation: The tree was empty, so the new node becomes the root.