Symmetric Tree

Given a binary tree, check whether it is a mirror of itself (ie, symmetric around its center).

For example, this binary tree is symmetric:

    1
   / \
  2   2
 / \ / \
3  4 4  3

But the following is not:

    1
   / \
  2   2
   \   \
   3    3

Note:
Bonus points if you could solve it both recursively and iteratively.

(Java Code on github at the bottom of the post. )

My thoughts and solutions:

This problem looks simple, but actually is a little tricky. Usually when I see a problem like this I immediately think of recursion and come to the following wrong conclusion: the whole tree is symmetric when subtrees are symmetric. I stuck with this idea for a few minutes and then realized that this is not true.

     1
   /   \
  2     4
 / \   / \
3   3 3   3

The subtrees of the tree above are symmetric but the whole tree is not.

How do we human check if something is symmetric? In this case, we would probably check one node on the left side and compare with node at its mirroring position on the right. If they are the same, we move on to another node. Otherwise it is not symmetric.

So we are actually traversing the trees and along the way we check if a certain pair of nodes in mirroring positions have the same value.

As for tree traversal, we have breadth-first and depth-first traversals. But we may have to make some modifications.

Using the following tree as an example:

     N1
   /   \
  N2    N3
 / \   / \
N4 N5 N6 N7
  • Breadth-First: in a normal situation, we would use a queue, starting from the root and keeping adding the child nodes.  The queue would be N1, N2, N3, N4, N5, N6, N7. But since we need the mirroring effect, the queue should be N1, N2, N3, N4, N7, N5, N6. So think about how to achieve this order when dealing with nodes. When comparing, we have to dequeue two nodes at a time (except for the root of the tree N1).
  • Depth-First: in this case, say we want to use recursion. Basically we traverse the left subtree from N2 and do the same for N3. We won’t be able to compare two nodes in mirroring position along the way. So we have to save the values somewhere. I say we use a stack. The order of the two traversals should be like this: left side should be N2, N4, N5 while right side should be N3, N7, N6. Each time we meet a node, we push its value to the stack and go to their child nodes. If a child node is null, we must push null to the stack too! Otherwise it will fail on the second example in this post.

Code on github:

Enhanced by Zemanta
Advertisements
Symmetric Tree

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s