How to check tree is a full binary tree

user_15789482 0
Viewed 56

such that fullA atr determines whether fullA atr is a full binary tree.

fullA :: AltTree a -> Bool
fullA (Leaf a) = True
fullA (One a b) = not (fullA b)
fullA (Two a b c) = fullA b && fullA c

It work for most of the example, But when I use example: fullA(One 0(One 1(Leaf 2))) It return True, but it should be return False. Can someone explain to me?

haskell
1 Answers

The line with (One a b) does not make much sense, since a full tree is defined as [wiki]:

A full binary tree (sometimes referred to as a proper or plane binary tree) is a tree in which every node has either 0 or 2 children.

This thus means that if your AltTree contains a One node, it is not a full binary tree. We thus can implement this as:

fullA :: AltTree a -> Bool
fullA (Leaf _) = True
fullA (One _ _) = False  -- we found a node with one one child
fullA (Two _ b c) = fullA b && fullA c

Note: In Haskell, it is common to use an underscore (_) for variables we do not care about. If we turn on the -Wunused-matches compiler flag, it will warn about patterns where the variables are not used at the right side of the equation.

user_675790
Related