Came across this question and wondering what the possible solutions will be:
A tree2 is ancestor preserving of tree1 if for any pair of nodes (node1, node2) in tree1 where node1 is the ancestor of node2, node1 is also a ancestor of node2 in tree2.
Left Tree Right Tree Check for right tree - True: B is ancestor of I, F and W
A B F is the ancestor of I
/ \ / \
B C G F
/ \ / \ / \ / \
E F D G X R I G
/ \ / /
W Y I W
Left Tree Right Tree Check for right tree - False: B is not ancestor of C, and I
A A W is not the ancestor of E
/ \ / \
B C B F
/ \ / \ / \ / \
E F D G W C I G
/ \ / /
W Y I E
Note: The nodes across both the trees may be different and in different order. The trees just need to preserve the Ancestor Descendent relationship for any pair of nodes from the first tree.Comments (9)