CODEWITHSUNDEEP
javadata-structures
yenyen
yenyen

Reputation: 35

how to merge two BST in java?

I need to merge two BSTs. If the given symbol table contains keys that is already in this symbol table merge overwrites those keys' values with the values in the given symbol table. but I'm completely lost of how I'm suppose to start.. All I have right now is the base case.

public class BST<Key extends Comparable<Key>, Value> {
private Node root;             // root of BST

private class Node {
    private Key key;           // sorted by key
    private Value val;         // associated data
    private Node left, right;  // left and right subtrees

    public Node(Key key, Value val) {
        this.key = key;
        this.val = val;
    }


public void merge(BST bst) {
    if(bst == null) return;
    // TODO
}

Upvotes: 1

Views: 611

Answers (1)

batman007
batman007

Reputation: 39

well i am not going to write the code for this problem. i can help you with the logic required to solve this problem tho

now think logically if you perform the inorder traversal of a BST And store each Node object in an array the resultant array will always be sorted.

step1:

so what you need to do here is perform the inorder traversal of the first tree and store each element in ar1(array1) . do the same for the second tree and store its elements in ar2(array2).

step2:

merge the two sorted arrays ar1 and ar2 into ar3.

step3: convert this sorted array into a BST now and you are done. but the question is how are u gonna do that? well its quite simple . inorder traversal again comes into play here.

1.Say mid is the mid­dle element in the array.

2.Recur­sively con­struct left sub­tree from start to mid-1

3.Make the mid­dle element as root and assign the left sub­tree to it.

4.Recur­sively con­struct right sub­tree from mid+1 to end.

5.Assign the right sub­tree to root.

have a look at this link your question is just a modified version of the question given here. sortedlistToBst

Upvotes: 1

Related Questions