How to check if a binary tree is complete-CodePudding

A binary tree is complete if the two sub-trees of every node are of equal size. Define a function that decides if a binary tree is complete.

I don't know how to write the next code, I think it is Leaf a == Node a, and then output a boolean value.
My Haskell code is show below:

data Tree a = Leaf a | Node a [Tree a]

judcomplete :: Tree a -> Tree a -> Bool
judcomplete (Leaf x) (Node y (Leaf z)) = Leaf x == Node y (Leaf z)

CodePudding user response：

Building on @Will-Ness's data type and solution we can take a similar but maybe more efficient approach.

The idea is that for a tree to be complete every sub tree must be complete. We can think of a post-order depth first search where we check the condition of each sub tree and pass it to their parent.

The conditions we need to check are:

Are the number of nodes in both sub trees equal?
Has this been the case for the sub trees of the sub trees?

Note that we need 2 types of information from each sub tree, one is the number of nodes in that sub tree, in order to compare it with the number of nodes in the other sub tree, and the other is a bool flag that indicates how this test of equality was in the sub trees of that branch.

This leads to a recursive solution with the base case being a Leaf. A leaf has a straight forward answer: It is complete by definition and has 0 nodes. So, we could return (True, 0) from all Leafs. None Leaf nodes do 2 things, compare the number of nodes in the left and right sub trees and also their bool values. If all these 3 conditions are true, they set the flag to true, otherwise false. They also add the number of nodes in the sub trees and increment them by one.

This leads to an O(n) solution where n is the number of nodes in the tree. I guess we can also implement it such that it lazily bails out of it finds a false along the way without diving down further recursive calls.

data Tree a = Leaf a | Node a (Tree a) (Tree a)


judComplete :: Tree a -> Bool
judComplete x = fst $ go x where
  go (Leaf _) = (True, 0)
  go (Node _ left right) = (leftTrue &&
                            rightTrue &&
                            leftCount == rightCount,
                            1   leftCount   rightCount) where
    (leftTrue, leftCount) = go left
    (rightTrue, rightCount) = go right

CodePudding user response：

First of all your data type is incorrect. It shows a multi-way tree whereas the problem is about binary trees.

Binary trees' nodes have two branches.

data Tree a = Leaf a | Node (Tree a) (Tree a)
                           -- left    right

A leaf-only tree is complete.

complete (Leaf _) = True

A tree represented by a node is only complete if both its branches are complete and are of the same size / depth:

complete (Node l r) = complete l && complete r
                        && sameDepth [l,r]

So as it turns out (and I didn't know this when I started typing this answer^(*)) sameDepth will explore the tree by levels! If all the trees in the current level are leaves, the depths were all the same along all the paths in the original tree:

sameDepth level = allLeaves level ||

Otherwise we must consider both branches of each node in its stead, in the next iteration. This iterative step must be guarded by a condition that all the trees in the level are nodes (why?):

                  allNodes level && sameDepth (replaceWithBranches level)

If the trees in the level were mixed -- some were leaves and some were nodes, then the original tree wasn't complete:

                 || False

This concludes the sameDepth definition.

What's left now is to implement allLeaves, allNodes, and replaceWithBranches. This should be easy enough to do either with list comprehensions or direct recursion.

The above might be grossly inefficient (see why? where? the gross inefficiency usually come from doing the same thing more than once). Perhaps you could improve it in that regard.

Also convince yourself that it is correct (or not).

^(*) This is how you could do it too. Don't panic! Don't think you must know the whole solution from the outset -- that way you won't write a line of code. Instead, just state some obvious facts that must be true. This way the code writes itself -- we use the non-existent functions which we wish were there, and that's how we discover which functions need to be written.

Optimization can come later. It can even come in a form of a complete re-write. The important thing is to not stop yourself from writing even the most grossly inefficient code. As long as it is "obviously" correct.