Erlang generic foldl/3 equivalent for binary trees

user_14713908 0
Viewed 123

I need to write the equivalent of lists:foldl/3 for binary trees.

Every node is represented as:

[Value, LeftNode, RightNode]

So a tree with a root 2 and leaves 1 and 3 would look like this: [2, [1, [], []], [3, [], []]]

Later I want to use that function to perform operations, such as summing up all positive values in that tree etc.

This is the function I wrote:

tree_foldl(_, Acc, []) -> Acc;
tree_foldl(Fun, Acc, [V, L, R]) ->
X1 = tree_foldl(Fun, Fun(V, Acc), L),
X2 = tree_foldl(Fun, Fun(L, X1), R),
X2.

the problem is that it's not truly generic, and when we have, let's say a tree with only a root, e.g.: [2, [], []]

it calls both Fun(2, 0) and Fun([], 2) and when trying to sum up the values in the second case it tries to do [] + 2, which is an invalid expression. It also would break on more complicated cases.

I would greatly appreciate any help with fixing this function. Thank you.

binary-tree erlang
1 Answers

First of all, you should use tuples as nodes in this case instead of lists. Lists are linked lists between their elements while tuples use contiguous memory (you can access a single element of a tuple without processing the leading elements of structure).

There's no need for Fun(L, X1):

tree_foldl(_, Acc, []) -> Acc;
tree_foldl(Fun, Acc, [V, L, R]) ->
    Acc0 = Fun(V, Acc),
    Acc1 = tree_foldl(Fun, Acc0, L),
    Acc2 = tree_foldl(Fun, Acc1, R),
    Acc2.

If the node is empty, do nothing, else run the Fun on the node and recurse on both subtrees.

user_21964560
Related