CODEWITHSUNDEEP
erlangbinary-search-tree
Sunny Dao
Sunny Dao

Reputation: 9

How to count the nodes which have exactly one child by using Erlang?

I have some problem when trying to find the node that has exactly one child, but the function doesn't return the right number (keep going return 0)

This is my code:

helper(Tree, Acc) ->
    case Tree of
    {Value, Left, Right} ->
     if
         {Value, Left, empty} -> helper(Left, Acc +1);
         {Value, empty, Right} -> helper(Right, Acc +1);
         {Value, Left, Right} -> helper(Left, Acc),
         helper(Right, Acc);
         true -> Acc
     end
    end.

Upvotes: 1

Views: 57

Answers (1)

Brujo Benavides
Brujo Benavides

Reputation: 1958

You have two issues:

  1. The if is unnecessary in your code, you can (and should) pattern-match directly on the case statement.

  2. You're not preserving the result of calling helper(Left, Acc) when calling heper(Right, Acc) in the third clause of your if/case.

I didn't test it, but I think your code should work if you write it like this:

helper(Tree, Acc) ->
    case Tree of
         {Value, Left, empty} -> helper(Left, Acc +1);
         {Value, empty, Right} -> helper(Right, Acc +1);
         {Value, Left, Right} -> helper(Right, helper(Left, Acc));
         _ -> Acc
    end.

As a matter of fact, you don't even need the case statement at all…

helper({Value, Left, empty}, Acc) -> helper(Left, Acc + 1);
helper({Value, empty, Right}, Acc) -> helper(Right, Acc + 1);
helper({Value, Left, Right}, Acc) -> helper(Right, helper(Left, Acc));
helper(_, Acc) -> Acc.

And, if you try to compile this, Erlang will promptly tell you that Value is unused everywhere. So, it would be better to write…

helper({_, Left, empty}, Acc) -> helper(Left, Acc + 1);
helper({_, empty, Right}, Acc) -> helper(Right, Acc + 1);
helper({_, Left, Right}, Acc) -> helper(Right, helper(Left, Acc));
helper(_, Acc) -> Acc.

But, to be fair… I think you are still missing a clause for {_, empty, empty}. Otherwise, you'll count that as a node with exactly one child when it actually has none…

helper({_, empty, empty}, Acc) -> Acc;
helper({_, Left, empty}, Acc) -> helper(Left, Acc + 1);
helper({_, empty, Right}, Acc) -> helper(Right, Acc + 1);
helper({_, Left, Right}, Acc) -> helper(Right, helper(Left, Acc));
helper(_, Acc) -> Acc.

Upvotes: 1

Related Questions