Binary tree equality

Source: Ashwin Krish

Why is it that for the equality checking of binary trees, an inorder + preorder or inorder + postorder traversal is done? How do these combinations ensure the equality of trees?

Let us think of the inverse problem. Let us construct a tree given the in-order and say pre-order traversals of a tree. The first element of pre-order will give you the root node. Because the root is always visited first. Now with only the pre-order we can only conclude that the rest of the elements belong to it’s subtrees. They do not tell whether they come in the left sub-tree or the right. But it is clear that only after all the left sub-tree is listed in the pre-order, the right subtree will be listed. We need to find till where is the left sub-tree and from where does the right begin.

A in-order traversal would tell us exactly that. Since we know which is the current root element, we can find the position of the same in the in-order. Now remember that in-order traversal is in the order left, root, right. So all elements to the left of the root in the in-order belong to the left. And so on. To construct the rest of the subtree. Given the number of elements in the left sub-tree that we got from the in- order, say k, we know the first k elements of inorder are in the left. And we can recurse.

The same can be done similarly for post order coupled with in-order.

The point to observe is that pre-order gives you the root. But doesn’t tell you about your sub tree. In order will give you which tree it belongs to but it doesn’t know the root. This is why it is essential to know both.

That's all ;)