Posts Merge two BST's (geeksforgeeks - SDE Sheet)
Post
Cancel

Merge two BST's (geeksforgeeks - SDE Sheet)

PROBLEM DESCRIPTION

Given two BSTs, return elements of merged BSTs in sorted form.

geeksforgeeks

SOLUTION

We can solve this by performing inorder traversals on both binary search trees to get sorted lists, then merging them using a two-pointer technique to create a single sorted list efficiently.

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
class Solution {

    public List<Integer> merge(Node root1, Node root2) {
        // Perform inorder traversal on both trees and merge the sorted lists
        return mergerSortedLists(inorder(root1, new ArrayList<>()), inorder(root2, new ArrayList<>()));
    }

    // Merges two sorted lists into one sorted list
    public List<Integer> mergerSortedLists(List<Integer> list1, List<Integer> list2){

        int i = 0;
        int j = 0;

        List<Integer> list = new ArrayList<>();

        while(i < list1.size() && j < list2.size()){
            if(list1.get(i) < list2.get(j)){
                list.add(list1.get(i));
                i++;
            } else {
                list.add(list2.get(j));
                j++;
            }
        }

        while(i < list1.size()){
            list.add(list1.get(i));
            i++;
        }

        while(j < list2.size()){
            list.add(list2.get(j));
            j++;
        }

        return list;
    }

    public List<Integer> inorder(Node root, List<Integer> list){

        if(root == null)
            return list;

        inorder(root.left, list);
        list.add(root.data);
        inorder(root.right, list);

        return list;
    }
}
This post is licensed under CC BY 4.0 by the author.