CODEWITHSUNDEEP
prologbinary-tree
coder123456789
coder123456789

Reputation: 9

Prolog - finding a common ancestor in a binary tree

Let's say you have a binary search tree:

t (73, t (31, t(5,nil,nil), nil), t (101, t (83, nil, t(97,nil,nil)), t(200,nil,nil)))

which is:

            73
         /     \
        31     101
       /      /   \
      5      83  200
                /
               97

I need to write a predicate subtree(X1,X2,T) that would take 2 values from the tree (X1 and X2) and find the smallest common parent for them, and store its subtree in T.

So for the example above, if I query : subtree(83,200,X).

I should be getting back:

t(101,t(83,nil,t(97,nil,nil)),t(200,nil,nil)) which is:

               101
              /   \
             83  200
                /
               97

Since 101 is the smallest common value to both of my numbers, I get that subtree back. How could I do that?

Thanks!

Upvotes: 0

Views: 490

Answers (1)

Ram Choudhary
Ram Choudhary

Reputation: 21

Here is my code for this problem. Just call

tree(X),common_ancestor(83,200,X,Y)

You will get your answer in Y.

tree3(X) :- X = t (73, t (31, t(5,nil,nil), nil), t (101, t (83, nil, t(97,nil,nil)), t(200,nil,nil))).

% Chech membership in tree:
in(X, t(X, _, _)).
in(X, t(_, L, _)):-
    in(X, L).
in(X, t(_, _, R)):-
    in(X, R).

% Getting subtree given the value of root 
get_subtree(X, t(X, L, R),Res) :- Res = t(X,L,R).
get_subtree(X, t(_, L, _),Res):-
    get_subtree(X, L,Res).
get_subtree(X, t(_, _, R),Res):-
    get_subtree(X, R,Res).

% least_common_ancestor(N1, N2, Tree, Res) assignes the value of the least common ancestor to Res.
% Note that it's assumed all nodes have different values.

% Base cases: when one value is the parent of the other, then the parent is the LCA:
least_common_ancestor(N1, N2, t(N1, L, R), N1):-
    (in(N2, L) ; in(N2, R)), !.
least_common_ancestor(N1, N2, t(N2, L, R), N2):-
    (in(N1, L) ; in(N1, R)), !.

% If one is in the left (right) subtree and the other is in the right (left) subtree then the current root is the LCA
least_common_ancestor(N1, N2, t(X, L, R), Res):-
    ((in(N1, L), in(N2, R)) ; (in(N1, R), in(N2, L))), !,
    Res = X.

% Otherwise, recurse to both subtrees:
least_common_ancestor(N1, N2, t(_, L, _), Res):-
    least_common_ancestor(N1, N2, L, Res), !. 
least_common_ancestor(N1, N2, t(_, _, R), Res):-
    least_common_ancestor(N1, N2, R, Res).


% The main function
commonGP(Ka,Kb,T,ST) :-
    least_common_ancestor(Ka,Kb,T,Res), get_subtree(Res,T,ST).

Upvotes: 2

Related Questions