I have been trying to figure out a way to compare two Binary Search Trees without multi-threading or any other such parallel computing means. The goal is to test the equivalence of two Binary Search Trees.
The definition of equivalence here is that the number of nodes must be same, and values contained in the two trees must be equal.
For example, see the attached image for two equivalent trees. Now, how would you test the equivalence of these programmatically?
One method I know of is to traverse the tree using any of the traversal methods - Inorder, Preorder, Postorder, etc. and then compare the results with the other tree's. One may even use a BFS or DFS algorithm.
Any other more efficient ways you can think of doing this?
PS: I am NOT in school. This is NOT a homework assignment. I graduated 3 years ago and I am brushing up on data structures. So please keep an open mind. Thanks!
Question
Jebadiah
I have been trying to figure out a way to compare two Binary Search Trees without multi-threading or any other such parallel computing means. The goal is to test the equivalence of two Binary Search Trees.
The definition of equivalence here is that the number of nodes must be same, and values contained in the two trees must be equal.
For example, see the attached image for two equivalent trees. Now, how would you test the equivalence of these programmatically?
One method I know of is to traverse the tree using any of the traversal methods - Inorder, Preorder, Postorder, etc. and then compare the results with the other tree's. One may even use a BFS or DFS algorithm.
Any other more efficient ways you can think of doing this?
PS: I am NOT in school. This is NOT a homework assignment. I graduated 3 years ago and I am brushing up on data structures. So please keep an open mind. Thanks!
Link to comment
Share on other sites
9 answers to this question
Recommended Posts