[SOLVED] Prolog - Find the depth of an element in a binary tree

Prolog - Find the depth of an element in a binary tree

I would like to know how I can find the depth of a given element E in a binary tree. For simplicity, the tree has no repeated elements.
I tried:

ElemDepth(E,t(E,T1,T2), D).
ElemDepth(E,t(M,T1,T2), D):- D1 is D+1, ElemDepth(E,T1, D1).
ElemDepth(E,t(M,T1,T2), D):- D1 is D+1, ElemDepth(E,T2, D1).

but it does not seem to work.

Solution

Given a binary tree where

The empty tree is denoted by the atom nil, and
A non-empty tree is represented as a t/3 structure:
```
t( Data, Left_Subtree, Right_Subtree)
```

We can walk it easily:

visit( t(_,L,_) , P ) :- visit(L,P). % visit the left subtree, then
visit( t(P,_,_) , P ) .              % visit the current tree node, then
visit( t(_,_,R) , P ) :- visit(R,P). % visit the right subtree

And visiting each node whilst computing the depth of the nodes is similarly easy. We just move the actual traversal logic into a helper predicate that carries with it the extra bit of state to count depth as it goes.

visit(T,P,D) :- visit(T,0,P,D) .

visit( t(_,L,_) , N, P, D ) :- N1 is N+1, visit(L,N1,P,D) .
visit( t(P,_,_) , D, P, D ) .
visit( t(_,_,R) , N, P, D ) :- N1 is N+1, visit(R,N1,P,D) .