CODEWITHSUNDEEP
javarecursionsearchtreebinary
Bergis
Bergis

Reputation: 85

Determine if an array will generate the same BST provided - Use Recursion

I have a problem that I am running into a few issues with, the question is as follows:

Given a pre-constructed Binary Search Tree and an array, determine if the array will produce the same Binary Search Tree.

Now, this question will have a pre-constructed BST for you, and then it will run through the following code:

boolean valid = true;
for (int i = 0;valid && i < arr.length; i ++) {
   valid &= tree.checkPattern(arr[i]);
}

//These two methods below are in a different class. For every element in the array,
//the checkPattern method will be called, initially passing in the root of the BST
public void checkPattern(int key) {
   recursiveFunction(root, key);
}

public boolean recursiveFunction(TreeNode current, int key){
 // Recursive function 
}

The goal is to write therecursiveFunction(root, arr[i]), and a hint is that the TreeNode class contains a visited boolean that you are to use to help with this algorithm.

I can't quite seem to figure out how to solve this... Given a key, are you supposed to check to see where it would go in the primary BST, and if the parent has already been visited, then return false?

Upvotes: 0

Views: 112

Answers (1)

Andreas
Andreas

Reputation: 159086

One way would be to build a new BST from the array, then compare the two trees. Think about how that builds the tree one node at a time.

Now, with a visited flag in every node, we start with all the flags being false, then the logic is:

  • For each value in the array, look for the node for that value (the target node) in the tree:

    • If the target node is not found, then answer is no (tree and array have different values).

    • If the path to the target node steps on any node that has not been visited yet, then answer is no (wrong order).

    • (optional) If the target node has already been visited, throw IllegalArgumentException (duplicate values in array not allowed).

    • Mark the target node visited.

  • Scan the tree (BFS or DFS, doesn't matter), and if you find any unvisited node, then answer is no (tree and array have different values).

  • If you get here, answer is yes.

Upvotes: 2

Related Questions