Merge Two BSTs
Advanced Problems DSA practice problem on Onlearn.
Difficulty: hard.
Topics: Merge 2 BST's, Binary Search Tree, Traversal, In-order Traversal, Recursion, Time Complexity, Space Complexity, Node, Pointer, Linked List, Arrays, Divide and Conquer, Sorting, Algorithm, Data Structures, binary search tree, inorder traversal, tree construction, merging sorted structures, linked list, Merging Sorted Data, Construct BST from Preorder.
Merge Two Binary Search Trees Problem Statement You are given the roots of two Binary Search Trees, root1 and root2. Your task is to merge these two trees into a single, balanced Binary Search Tree. The resulting BST should contain all nodes from both original trees, preserving the BST property. If there are duplicate values, they should all be included in the merged tree. Input Specification The input consists of two pointers, root1 and root2, pointing to the root nodes of the two Binary Search Trees. Each node in the trees typically has an integer value, a pointer to its left child, and a pointer to its right child. Output Specification Return a pointer to the root node of the new, merged, and balanced Binary Search Tree.