99 Clojure Problems – 59: Construct Height-Balanced Binary Trees

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

Write a method to construct height-balanced binary trees for a given height with a supplied value for the nodes. The function should generate all solutions."

Example

ninety-nine-clojure.bintrees> (height-balanced-trees 2 'x)
([x [x nil nil] [x nil nil]] [x [x nil nil] nil] [x nil [x nil nil]])

Discussion

To get some intuition for this problem we can distinguish tree cases:

1. The left subtree has the same length as the right subtree
2. The left subtree is shorter by one level
3. The right subtree is shorter by one level

If we combine all three cases via concat we have our solution. We generate the solutions by recursively calling the function with the heights h-1 and h-2. We don't have to generate the 'short' versions of the left and right subtrees separately. We can just create both combinations (left shorter/right shorter) with just one copy of the lower subtrees (h-2) and one copy of the higher subtrees (h-1). Still, there is some redundant computation going on as the h-1 contains also the h-2 subtrees. Memoization might help here.

The practical applicability of the function just created as described is somewhat limited as the number of height balanced binary trees grows exponentially. For our test case we therefore just look at trees up to five levels high.

Read more about this series.

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.

99 Clojure Problems－54: Is This A Binary Tree?

"Write a predicate tree? that succeeds if and only if its argument is representing a binary tree."

Example/Test

(deftest nil-is-a-tree
  (is (= true (tree? nil))))

Discussion

This is an interesting problem because it allows us to touch the basic question of static vs. dynamic typing.

If we look at the Scala solution, we see that in a statically typed language this problem can be fully solved via the type system. Or as Phil Gold put it: "Score one for static typing."

I am not a zealot when it comes to static vs. dynamic typing. Both approaches have their merits. There are many ways to look at this (prototyping, easier code reuse vs. working with legacy code, catching errors early ...). Maybe it is a very narrow perspective but for me it is almost more of a social than a technical issue. I see how a team of developers with mixed skill levels in combination with a code base in various stages of decay can benefit from a compiler giving them more guidance along the way through the maze. On the other hand, I have never missed the absence of a strict type system in Clojure when quickly building prototypes or solving programming problems. While I am still on the fence about the general issue of static vs. dynamic type systems, let us look at the problem at hand: working with binary trees.

The Dynamic Approach

We can solve this problem in a "dynamic" fashion building upon what we have done so far in this series. We worked with trees before for problem 25 using a library called core.match, which gives us pattern matching in Clojure to implement all the tree operations.

With core.match we get the tree?-predicate with a simple three way pattern match: it is either a node consisting of a label and two subtrees or nil representing the empty tree. Everything else is not a tree. The only complication is that we need to apply the pattern match for the node recursively, because the left and right subtrees should also be proper trees. Luckily, core.match supports function application in match expressions since 0.3.0.

Have a look at the solution and the accompanying tests to the get the idea.

Best of Both Worlds?

In Clojure we have a second option because, while being dynamic as a language, it offers us optional static typing in the form of a library called core.typed. The library is the result of the work Ambrose Bonnaire-Sergeant did for his PhD dissertation.

It allows us to declare a type Node consisting of a label of any kind and two children that are trees themselves. A tree is now either an empty tree (represented by nil) or one of these nodes.

(t/ann-datatype Node [val :- Any
                      l   :- Tree
                      r   :- Tree])
(deftype Node [val l r])

(t/defalias Tree
  (t/Nilable Node))

To make this work, all you have to do is include core.typed as a library dependency in your project.clj (assuming you are using leiningen as your build tool). The type checking is not part of the compilation but an extra step you have to integrate into your workflow. Editor integrations for vim, Emacs and LightTable make it easier to construct your type system during development.

It helps to look at the core.typed example code (even if you are familiar with static typing) to work out how to apply the type annotations.

The Choice Is Yours

Clojure seems to give us the choice between both (optional) static and dynamic typing. If time allows, I will try to follow this dual path through all the binary tree problems to gain more insight into both approaches.

Read more about this series.