CODEWITHSUNDEEP
haskellrecursion
Stephen Adams
Stephen Adams

Reputation: 225

In Haskell, how do I return the number of nodes in a binary tree?

Define, for a binary tree type Tree, a function which returns the number of nodes. I came up with this function but it does not run.

Error: Not in scope: data constructor'Node'

numberOfNodes :: Tree -> Int
numberOfNodes Null = 0
numberOfNodes (Node _ st1 st2) = 1 + max (st1)(st2)

Upvotes: 0

Views: 866

Answers (3)

willeM_ Van Onsem
willeM_ Van Onsem

Reputation: 476567

The error indicates that you did not make a data constructor Node. Perhaps you made a data constructor Tree, for example:

data Tree a = Null | Tree a (Tree a) (Tree a)

using Tree as a data constructor is not wrong. But you need to decide what the name will be, and use that data constructor.

Anyway, you do not need to define a function to count the number of elements yourself. You can let Haskell make it an instance of Foldable, and then use length :: Foldable f => f a -> Int:

{-# LANGUAGE DeriveFoldable #-}

data Tree a = Null | Node a (Tree a) (Tree a) deriving (Foldable, Show)

If we for example define a sample tree like @AndyG wrote, we can calculate the number of Nodes as:

Prelude> length (Node 0 (Node 1 Null Null) (Node 2 Null Null))
3

If you implement the length yourself, you should make a recursive call to the subtrees, since you can not add up subtrees:

numberOfNodes :: Tree -> Int
numberOfNodes Null = 0
numberOfNodes (Node _ st1 st2) = 1 + numberOfNodes st1 + numberOfNodes st2

Upvotes: 2

Will Ness
Will Ness

Reputation: 71065

It seems you don't have the data type definition in scope. It should probably be 

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

Also, the code you show computes a tree's depth (in principle, after it's fixed). The total count of tree's nodes is the sum of the counts of nodes in its left and right sub-trees, give or take 1; not max.

Empty (leaf, Null) nodes should probably not be counted, i.e. their contribution to the total count should probably be 0. You decide.

Upvotes: 1

AndyG
AndyG

Reputation: 41092

The first issue is that you appear to be missing a definition for what a Tree is.

Generally we say it's either a Node with a value plus two subtrees, or it's empty.

Next, our recursive definition for the number of nodes in a (non-empty) tree should be:

number of nodes in left subtree + number of nodes in right subtree + 1

Here is a full definition:

data Tree a = Empty | Node a (Tree a) (Tree a) deriving (Show)
numberOfNodes :: Tree x -> Int
numberOfNodes Empty = 0
numberOfNodes (Node _ st1 st2) = 1 + numberOfNodes(st1) + numberOfNodes(st2)

(Note that we implement the Show typeclass so that we can print the tree)

If we define a binary tree with 3 nodes, see how it works:

myTree :: Tree Int
myTree =
   Node 0
      (Node 1 Empty Empty)
      (Node 2 Empty Empty)

> numberOfNodes myTree
=> 3

Live Demo

Upvotes: 2

Related Questions