If I have two binary trees, how would I check if the elements in all the nodes are equal.
Any ideas on how to solve this problem?
+6
A:
You would do a parallel tree traversal - choose your order (pre-order, post-order, in-order). If at any time the values stored in the current nodes differ, so do the two trees. If one left node is null and the other isn't, the trees are different; ditto for right nodes.
Jonathan Leffler
2009-06-15 02:02:35
Two binary search trees with identical items are allowed to be different in in-order walk (root 2, left 1; vs, root 1, right 2), unless further conditions yet are imposed; so I suggest you edit your answer to avoid suggesting the (incorrect, net of further conditions) use of in-order (pre-order is fine, of course).
Alex Martelli
2009-06-15 02:08:36
The question isn't about whether the information content is equivalent, but whether the values are the same at the corresponding node in each tree. You are, I believe, trying to answer a different question from the one asked.
Jonathan Leffler
2009-06-15 02:33:46
I'm checking if the elements in ALL the nodes (which intrinsically form a set) are equal, as opposed to checking if the element in EVERY corresponding node is equal. The question was asked with ALL, *NOT* with EVERY, so I'm not the one answering a question that wasn't asked.
Alex Martelli
2009-06-15 03:01:44
@Alex: OK; then we are using nominally the same language to mean different things. I don't understand the distinction you are making between ALL and EVERY - they're essentially synonyms in my version of English and this context (and most others too).
Jonathan Leffler
2009-06-15 05:13:32
In the case that we are comparing the structure of two trees (i.e. - is each corresponding node identical) wouldn't the only applicable search be an in-order traversal? Pre-order and post-order traversals can produce the same results for trees that are not identical (but contain the same elements) unless you are keeping track of the depth of recursion (which is pointless when you can do that with an in-order traversal).
Niki Yoshiuchi
2009-06-15 14:40:15
@Niki: It depends on the cost of the comparison versus the cost of the traversal. Suppose that you are storing 3D vector images in the nodes; comparing whether two 1 MB chunks of data are the same when the difference is at offset 750 KB is costly, but looking at the shape of the structure via the child nodes is cheap - this argues for a post-order traversal since you only look at the value in the current node when you know the sub-structures are identical. If the comparisons are cheap (eg comparing two 4-byte integers) then the in-order processing makes sense.
Jonathan Leffler
2009-06-15 18:50:06
+1
A:
you could use something like Tree Traversal to check each value.
contagious
2009-06-15 02:03:08
A:
If the trees are binary search trees, so that a pre-order walk will produce a reliable, repeatable ordering of items, the existing answers will work. If they're arbitrary binary trees, you have a much more interesting problem, and should look into hash tables.
Alex Martelli
2009-06-15 02:05:59
To add to that, if it's a binary search tree, then it's sufficient to check the left most leaf and the right most leaf since they are the smallest and largest values in the tree :)
Charles Ma
2009-06-15 02:09:11
...and how does that ensure that all the values in between are also exactly the same, @cma...?
Alex Martelli
2009-06-15 02:31:55
@Alex - granted, if the question was about whether the information content in arbitrary trees was equivalent, then there'd be much more work to do. The question doesn't seem to be about that. You are over-complicating it.
Jonathan Leffler
2009-06-15 02:39:40
As per my comment on your answer, the question NEVER mentioned binary SEARCH trees (everybody's just reading the questioner's mind about that, apparently -- I'm the only one trying to CHECK) -- plus, there's a big, important different between "the elements in all the nodes" (what's being asked) and "the single element in each and every corresponding node" (what everybody's answering about). If the questioner erred badly in phrasing, he can edit the question, but why is everybody just ASSUMING that he erred badly instead of expressing himself correctly and precisely?!
Alex Martelli
2009-06-15 03:05:12
@Alex: my answer makes no assumptions about it being a binary search tree whatsoever. You can traverse any binary tree in any of the orders I listed. What I outlined as an algorithm ensures both that the shapes of the two trees are identical, and that the value stored in each node of tree 1 is the same as the value stored in the (equivalent) node of tree 2. Since we clearly are not having a meeting of minds, I will not add any more comments after this one - and I'm not certain I should have added this comment.
Jonathan Leffler
2009-06-15 06:13:03
Which countries teach Binary Trees or BSTs in C? Poor students. I'd guess it's not binary search trees but plain binary trees, maybe even non-balanced ones
Chris S
2009-06-15 15:02:14
@Jonathan, ensuring identical shapes (as well as equal sets of items) is clearly one possible task, but so is the different task of ensuring just the equal sets, so what it boils down to is, we read the original question differently -- I saw no mention of identical shapes in it.
Alex Martelli
2009-06-15 16:08:13
@Chris, what's so bad about teaching fundamental data structures in C? And several kinds of trees surely qualify as "fundamental".
Alex Martelli
2009-06-15 16:08:59
+1
A:
Hello!
Does node order matters? I'm assuming for this answer that the two following trees :
1 1
/ \ / \
3 2 2 3
are not equal, because node position and order is taken into account for the comparison.
A few hints
- Do you agree that two empty trees are equal?
- Do you agree that two trees that only have a root node, with identical node values, are equal?
- Can't you generalize this approach?
Being a bit more precise
Consider this generic tree:
rootnode(value=V)
/ \
/ \
-------- -------
| left | | right |
| subtree| |subtree|
-------- -------
rootnode is a single node. The two children are more generic, and represent binary trees. The children can either be empty, or a single node, or a fully-grown binary tree.
Do you agree that this representation is generic enough to represent any kind of non-empty binary tree? Are you able to decompose, say, this simple tree into my representation?
If you understand this concept, then this decomposition can help you to solve the problem. If you do understand the concept, but can't go any further with the algorithm, please comment here and I'll be a bit more specific :)
NicDumZ
2009-06-15 02:29:21
@NicDumZ, you're checking equality _of structure_, NOT, as specified, equality of all elements; see my comment to @Jonathan very popular (and still wrong, until he edits it;-) answer for a case in which (net of other constraints) two binary search trees with the same elements have different structure. (Plus, see my answer: binary search trees are NOT the same set as binary trees!-)
Alex Martelli
2009-06-15 02:34:43
@Alex - you are trying to answer a different question from the one asked; NicDumZ is doing fine on the question at the top.
Jonathan Leffler
2009-06-15 02:37:30
@Alex, I know. And I added an introduction to my answer to reflect that ;) I believe that this is a beginner question, and that the OP might want to do exactly this. As for binary search trees, I cannot see "search" anywhere in the question? :)
NicDumZ
2009-06-15 02:39:17
A:
My solution would be to flatten the two trees into 2 arrays (using level order), and then iterate through each item and compare. You know both arrays are the same order. You can do simple pre-checks such as if the array sizes differ then the two trees aren't the same.
Level Order is fairly easy to implement, the Wikipedia article on tree traversal basically gives you everything you need, including code. If efficiency is being asked for in the question, then a non-recursive solution is best, and done using a FIFO list (a Queue in C# parlance - I'm not a C programmer).
Chris S
2009-06-15 14:56:34