2 binary trees are equal or not

Question

Possible duplicate:
Determine if two binary trees are equal

Got an interview yesterday, the question got me, here it is:

Description

There are 2 binary trees , check if they are equal.

They are equal if and only if tree1->child == tree2->child and one tree left and right children can be swapped with each other .

For example:

  5 6 / \ / \ they are equal. 1 2 2 1 5 6 / \ / \ they are equal. 1 2 2 1 / \ / / 3 4 4 3 

Any ideas are welcome.

Answer 1

I do not think this is an unreasonable question. A simple recursive solution is

 boolean equals(x, y) { if (x == null) { return y == null; } if (y == null) { return false; } if (x.val != y.val) { return false; } if (equals(x.left, y.left) && equals(x.right, y.right)) { return true; } if (equals(x.left, y.right) && equals(x.right, y.left)) { return true; } return false; } 

This can be very expensive, for example, if we have two large trees of the same shape, where all non-leaf nodes have the same associated value, and the leaf nodes of one are a permutation of the leaf nodes of the other.

To get past this, you can first change left and right as necessary, so that left <on the right, for some recursive definition of <. It can also be costly, but much less than checking every permutation, and I think choosing a definition of <would help. This will allow you to verify equality with the usual definition.

This concept of http://en.wikipedia.org/wiki/Canonicalization , followed by ordinary equality, also solves the question of whether you really have an equivalence relation. The equivalence relation is equivalent to a partition. Ordinary equality is obviously a section. If you compare x and y by comparing f (x) and f (y) followed by an equivalence relation, you have a partition of x and y and therefore an equivalence relation.

After thinking about this, I think that the way to make canonicalization or uniform testing reasonably effective is to work from the bottom up, annotating each node with a token whose value reflects the result of comparisons with other nodes, so that you can compare nodes and subtrees under them, just compare tokens .

Thus, the first step for equality is, for example, use a hash table to annotate each leaf with tokens that are equal only when the values ​​in the leaves are equal. Then, for nodes in which only children are leaves, they use, for example, a hash table to assign additional tokens so that the markers in these nodes are equal only when the leaves, if any, under these nodes match. Then you can go one step further, and this time you can compare tokens in child nodes, rather than recursing down the tree. The cost of assigning tokens in this way should be linear in the size of the trees involved. At the top, you can compare trees by simply comparing tokens in the root.

Answer 2

The equality operators are transitive: if A = B and B = C, then A = B = C, therefore A = C.

The equality operators are reflexive: A = A, B = B, and C = C, regardless of their values.

The equality operators are symmetric. If A = B, then B = A. (It doesn't matter what order they are in.)

Now, looking at the definition that they gave you:

A tree is equal to another tree if the children are equal. We'll see. We can assume that the nodes are compared below, otherwise the definition is pretty useless. But they did not bother to tell you how to resolve this comparison, and the whole definition that they gave you depends on it.

In short, this is a shitty question.

Let's see what happens if we decide that we want to try to figure this out.

But wait, they will also tell you that two children of any tree can be replaced. This adds the limitation that any tree equal to something else (including itself) should be equal to its mirror image. And any variations of his subtree children change places.

And remember that this should be a search tree. Therefore, we can assume that two different search trees that are processed by the same algorithm should give the same result if they are equal. Thus, if we switch around the elements of the tree, this will affect the search time. Thus, trees that do not have each node in place are not equal to each other.

Assuming this along with the “replaceable” property of this equality, we can see this as an invalid definition of equality. (If we try to apply it, it turns out that only trees that have the same node for each node at a certain level are equal and only for themselves, which breaks part of the reflexivity of the equality operator.)

Answer 3

If you implement your definition of “equality” with flip invariance, you violate the definition of equality. The definition doesn’t even make sense, since that’s not how binary search trees are equal (unless each node has a pointer to which subtree is “bigger” and which is “less”).

You have two options for reasonable definitions:

• topological (flip-agnostic) equivalence (in this case you cannot call it a “binary search tree” because it is not sorted):

  tree1==tree2 means set(tree1.children)==set(tree2.children)

• normal normal search tree (flip care) equivalence:

  tree1==tree2 means list(tree1.children)==list(tree2.children)

For binary trees, the above definitions will work as written in any language that supports list and set data types (python sets will throttle, however, to non-displayable data types). However, here are some more detailed and ugly C / Java-like definitions:

• topological equivalence:

  t1==t2 means (t1.left==t2.left and t1.right==t2.right) or (t1.left==t2.right and t1.right==t2.left)

• sorted tree equivalence:

  t1==t2 means (t1.left==t2.left and t1.right==t2.right)

The definitions given above are recursive; that is, they suggest that equality has been defined for the subtrees and basic affairs that he has.

---

Sidenote:

quote: tree1-> child == tree2-> child

This is not a valid statement because the node tree does not have a single child.

Answer 4

Compare trees using the canonicalization approach proposed by @mcdowella . The difference is that my approach does not require O(N) additional memory wrt the number of nodes in the tree:

 # in Python from collections import namedtuple from itertools import chain # Tree is either None or a tuple of its value and left, right trees Tree = namedtuple('Tree', 'value left right') def canonorder(a, b): """Sort nodes a, b by their values. `None` goes to the left """ if (a and b and a.value > b.value) or b is None: a, b = b, a # swap return a, b def canonwalk(tree, canonorder=canonorder): """Yield all tree nodes in a canonical order. Bottom-up, smaller children first, None is the smallest """ if tree is not None: children = tree[1:] if all(t is None for t in children): return # cut None leaves children = canonorder(*children) for child in chain(*map(canonwalk, children)): yield child yield tree 

canonwalk() requires O(N*M) and O(log(N)*M) steps to get all the nodes in the tree, where N is the total number of nodes, M number of children, each of which has a node (it is 2 for binary trees).

canonorder() can be easily generalized to any node representation and any number of children. canonwalk() only requires that the tree can access its immediate children as a sequence.

Comparison function calling canonwalk() :

 from itertools import imap, izip_longest unset = object() def cmptree(*trees): unequal = False # allow root nodes to be unequal # traverse in parallel all trees under comparison for nodes in izip_longest(*imap(canonwalk, trees), fillvalue=unset): if unequal: return False # children nodes are not equal if any(t is unset for t in nodes): return False # different number of nodes if all(t is not None for t in nodes): unequal = any(nodes[-1].value != t.value for t in nodes) else: # some are None unequal = any(t is not None for t in nodes) return True # equal 

Example

  5 6 / \ / \ they are equal. 1 2 2 1 / \ / / 3 4 4 3 tree1 = Tree(5, Tree(1, Tree(3, None,None), None), Tree(2, None, Tree(4, None, None))) tree2 = Tree(6, Tree(2, Tree(4, None, None), None), Tree(1, Tree(3, None, None), None)) print cmptree(tree1, tree2) 

Exit

 True 

Answer 5

I read the questions like: for two deep trees, for each depth in the tree, find out if their children are set on top of each other.

This can be encoded relatively easily.

Answer 6

Ruby-free recursion solution

 def same? top_t1, top_t2 for_chek << [top_t1, top_t2] # (1) put task for check into queue while t1,t2 = for_check.shift # (2) return false unless t1.children.count == t2.children.count # generally for non-binary tree, but also needed for controlling of nil children break if t1.children.empty? t1_children = t1.children.sort # this is sorted arrays t2_children = t2.children.sort # of childrens return false unless t1_children == t2_children # (3) 0.upto(t1_children.count - 1) do |i| for_check << [t1_children[i], t2_children[i]] # put equivalent child pairs into queue end end return true end 

Ruby syntax tips:

• (1) placing an element in an array: arr << elem ; in this case for_check is an array of arrays
• (2) concurrent assignment: t1,t2 = [item1, item2] . Same as arr = [item1, item2]; t1 = arr[0]; t2 = arr[1] arr = [item1, item2]; t1 = arr[0]; t2 = arr[1]
• (3) t1_children == t2_children assumed the appropriate behavior == for this type of object. More detailed will be t1_children.map { |el| el.val } == t2_children.map { |el| el.val } t1_children.map { |el| el.val } == t2_children.map { |el| el.val } t1_children.map { |el| el.val } == t2_children.map { |el| el.val } - here map creates an array of vals.