Insert into a Binary Search Tree
Insert into a Binary Search Tree is a Medium Data Structures and Algorithms interview problem you can solve, run and submit on Thita.ai. It belongs to the Tree Traversal Patterns (DFS & BFS) pattern, in the Recursive Preorder Traversal subpattern.
Problem statement
A binary search tree (BST) is a binary tree in which every value in a node's left subtree is smaller than the node's value, and every value in its right subtree is larger. Each node may have zero, one, or two children. The root parameter is the root of the existing BST, represented in the input as a level-order array; null denotes a missing child.
Insert the integer in val while preserving the BST property. The value in val does not already occur in the tree. The usual result places val in a newly created leaf at the first available position along its search path, although any valid BST containing all original values and val is accepted.
Return the root of the resulting BST. If root is empty, create a single-node tree containing val. The returned tree is represented in level order, using null for missing children.
Example 1:
Input: root = [8,3,10,1,6,null,14], val = 7 Output: [8,3,10,1,6,null,14,null,null,null,7] Explanation: Since 7 is less than 8 but greater than 3 and 6, it becomes the right child of 6.
Example 2:
Input: root = [], val = 12 Output: [12] Explanation: An empty tree receives a new root node containing 12.
Example 3:
Input: root = [5,2,9,null,4,7,11], val = 1 Output: [5,2,9,1,4,7,11] Explanation: The search moves left from 5 and then left from 2, so 1 is attached as the left child of 2.
Constraints:
- 0 <= number of nodes in root <= 10^4 - -10^8 <= value in each tree node <= 10^8 - -10^8 <= val <= 10^8 - root is either empty or represents a valid binary search tree - All values already present in root are distinct - val does not already exist in root
Topics and companies
Topics: Binary Search Tree, Binary Tree, Tree, Pointers.
How to practise Insert into a Binary Search Tree on Thita.ai
Starter code is provided in C#, C++, Go, Java, JavaScript and Python. Your solution runs against 5 test cases for this problem, with the AI coach available for a hint when you are stuck rather than a finished answer. The reference solution runs in O(h), where h is the height of the tree. time and O(h) for the recursion stack. space.
Open Insert into a Binary Search Tree in the code editor, or read the Insert into a Binary Search Tree editorial for a worked solution with its approach and complexity analysis.
Where Insert into a Binary Search Tree sits in the DSA pattern sheet
- Tree Traversal Patterns (DFS & BFS) pattern guide
- Recursive Preorder Traversal subpattern
- The full DSA patterns sheet
- All coding practice problems
Problems related to Insert into a Binary Search Tree
Other problems that use the same Recursive Preorder Traversal and Tree Traversal Patterns (DFS & BFS) techniques:
- Binary Tree Paths — Easy, same subpattern
- Binary Tree Preorder Traversal — Easy, same subpattern
- Construct Binary Tree from Preorder and Inorder Traversal — Medium, same subpattern
- Construct Quad Tree — Medium, same subpattern
- Count Good Nodes in Binary Tree — Medium, same subpattern
- Flatten Binary Tree to Linked List — Medium, same subpattern