99 Clojure Problems – 58: Generate-and-Test Paradigm

"Apply the generate-and-test paradigm to construct all symmetric, completely balanced binary trees with a given number of nodes.

How many such trees are there with 57 nodes? Investigate about how many solutions there are for a given number of nodes? What if the number is even? Write an appropriate function."

Example

>(symmetric-cbalanced-trees 5 'x)
([x [x nil [x nil nil]] [x [x nil nil] nil]] [x [x [x nil nil] nil] [x nil [x nil nil]]])

Discussion

A simple approach just filters the output of our existing function for completely balanced trees using the also existing symmetric? predicate.

A simple optimisation is to avoid the tree generation all together if the number of nodes requested is even, as there is no symmetric tree with an even number of nodes.

Solution on Github.

Read more about this series.

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.

99 Clojure Problems – 57: Binary Search Trees

Write a function insert-val to add elements to a binary search tree. Then write a function to construct a binary search tree from a list of integer numbers. Then use this function to test the solution of the problem P56.

Example

>(->binary-search-tree 3 2 5 7 1)
[3 [2 [1 nil nil] nil] [5 nil [7 nil nil]]]
>(->binary-search-tree 5, 3, 18, 1, 4, 12, 21)
[5 [3 [1 nil nil] [4 nil nil]] [18 [12 nil nil] [21 nil nil]]]
> (symmetric? *1)
true

Discussion

I feel almost bad about the number of times I have resorted to core.match to solve these problems. Maybe I am just not thinking hard enough about alternative approaches. What it certainly tells us is that pattern matching seems to lend itself very well to this class of problems.

Pattern Match All The Things

Four match clauses seem to do the trick (number three is technically split into two) :

1. Adding nil to a tree is just the tree.
2. Adding a value to nil is a new tree of one node
3. Adding a non-nil value to a non-nil tree: Now it depends on the ordering of the values: is the value greater than the value at the current node: add it to the right subtree, else add it to the left subtree.

What about adding the same value twice? I do not think binary search trees are per se opinionated about how to handle duplicates. In my implementation duplicate values just end up to the right of the value they are identical with. I think it would also be very plausible to make insert-val a no-op if the value is already contained in the tree.

Putting it all together

Constructing the tree seems trivial using the insert-val function we have just constructed. Clojure's reduce is equivalent to a 'fold left' over the input collection. If we reduce the input values with insert-val using nil as the neutral element we get the desired result.

My solution can be found, as always, on Github.

Read more about this series.

99 Clojure Problems – 55: Construct Completely Balanced Binary Trees

"In a completely balanced binary tree, the following property holds for every node: The number of nodes in its left subtree and the number of nodes in its right subtree are almost equal, which means their difference is not greater than one."

Example

>(balanced-trees 3 'x)
([x [x nil nil] [x nil nil]])

Verification

(defspec balanced-trees-are-balanced
  20
  (prop/for-all [i gen/nat]
                (->> (balanced-trees i 'x)
                     (apply  breadth-first-traverse)
                     (map balanced?)
                     (reduce #(and %1 %2)))))

Discussion

The following observations lead to a possible solution:

1. We can enumerate all the trees by combining the root node with all its possible subtrees to the left and to the right which have in sum \(n-1\) nodes
2. We distinguish between even and odd values of n
3. Odd values of n give balanced trees as \(n-1\) is even and both subtrees will be of equal size
4. Even values of n give balanced trees if we return all combinations of left/right trees with \((n-1) / 2\) and \((n-1) / 2 + 1\) nodes. We are using integer division here, thereby effectively 'flooring' and 'ceiling'

Based on this understanding the implementation is fairly straightforward. We handle the base case of an empty tree separately and then the two cases for odd and even number of nodes.

There is a little bit of ceremony involved in order to create the combinations of subtrees in the case of odd-sized subtrees. You have to do a nested mapcat to get both variants with the longer subtree in left and right position respectively. Maybe there is room for improvement.

I found it instructive to look at the Haskell and Prolog solutions in order to get a better understanding. The latest version of my code tries to come close to the clarity of the Prolog solution.

Read more about this series.