CODEWITHSUNDEEP
erlang
MJah
MJah

Reputation: 43

In Erlang, how to write a BFS Tree Search to find a specific node

I want to write a function to find a specific node in a BFS Tree Search.

How to do it in Erlang?

Upvotes: 3

Views: 755

Answers (1)

Adam Lindberg
Adam Lindberg

Reputation: 16577

Assuming a simple structure:

node() :: {Key :: term(), Left :: node(), Right :: node()} | undefined.

This function would perform a breadth-first search over the tree and return the depth of the first element found (returns false if no node is found):

find(_Key, undefined) -> false;
find(Key,  Tree)      -> find(Key, [Tree], [], 0).

find(_Key, [], [], _Depth) -> % No more children
    false;
find(Key, [], Children, Depth) -> % Next level, increase depth
    find(Key, Children, [], Depth + 1);
find(Key, [{Key, _, _}|_Rest], _Children, Depth) -> % Found it!
    Depth;
find(Key, [{_, Left, Right}|Rest], Children, Depth) -> % Add children to search
    find(Key, Rest, add(Right, add(Left, Children)), Depth).

add(undefined, List) -> List;
add(E,         List) -> [E|List].

(An empty tree is just undefined).

Upvotes: 5

Related Questions