99 Clojure Problems – 56: Symmetric Binary Trees

"Let us call a binary tree symmetric if you can draw a vertical line through the root node and then the right subtree is the mirror image of the left subtree. Write a predicate symmetric/1 to check whether a given binary tree is symmetric. Hint: Write a predicate mirror/2 first to check whether one tree is the mirror image of another. We are only interested in the structure, not in the contents of the nodes."

Example/Test

(deftest p56-symmetric-binary-trees
  (is (= true (symmetric? [:a [:b nil nil] [:c nil nil]])))
  (is (= false (symmetric? [:a nil [:b nil nil]]))))

Discussion

This is a two star problem but once the implications of 'symmetry' in this case become clear, it is not hard at all to solve.

If we think about the tree it is obvious that we cannot establish the property of symmetry just by looking at the node count. Symmetry seems to be stricter in that it not only requires the same number of nodes in each subtree but they also have to be mirror images of each other. This is already implied in the hint given to us in the problem description.

Another way of putting it is that the leaves of the subtrees we compare have to be in the mirrored position respectively. One way to find that out is to recursively inspect both subtrees and make sure that there is a leaf in left tree when there is also a leaf in the right tree.

This led to this solution, which is incorrect.

Nil-Punned

The reason this first solution does not work as expected is that I have overloaded the meaning of nil. It represents the absence of a subtree and the empty tree. But I have also created the helper functions 'lefts' and 'rights' to extract the left or right subtrees respectively. As they rely on the seq abstraction through 'first', 'next' and 'last', nil now can be also the result of retrieving one of the subtrees.

There is no way to decide if the nil we get back means now 'there is no subtree' or 'there is no subtree because there is no tree in the first place'. But exactly this distinction is important when we want to determine the symmetry property of the data structure.

(Data) Structure

Pattern matching using core.match on the structure of the tree allows us to overcome this problem and distinguish the different cases more clearly. Nil as the empty tree never matches the pattern for a tree node. We do not need the different helper functions anymore as we are now working directly with the structure of our data.

You can find this amended solution on Github.

Read more about this series.