CODEWITHSUNDEEP
prolog
user3109560
user3109560

Reputation: 23

Logic Issue with custom binary search tree

I am trying to define a simple binary search tree. It is stored in lists like so: [Key, Left Tree, Right Tree]. I'm having issue with my logic. This is what I have

bstadd(K, [], [K,[],[]]).
bstadd(K, [X|_], [X, [], [K, [], []]]) :- K > X.
bstadd(K, [X, [], [K, [], []]], [X|_]) :- K < X.

This is what I query 

1 ?- bstadd(19, [],T1), bstadd(20,T1,T2), bstadd(21,T2,T3).

this is what I get out

T1 = [19, [], []],
T2 = [19, [], [20, [], []]],
T3 = [19, [], [21, [], []]]

and this is what I need

[19, [], [20, [], [21, [], []]]]

Any help would be wonderful. I have been banging my head against the wall for days.

Upvotes: 2

Views: 93

Answers (1)

ssbarbee
ssbarbee

Reputation: 1712

This is my solution. Let me know what you think and if you find it hard to understand it I'll be glad to help you out.

bstadd(Value, [], [Value,[],[]]).
bstadd(Value,[Key,Left,Right],X) :- Value \= Key , % no duplicates in BST
                                    (
                                      Value < Key -> % if Value < Key
                                        % then add to left side
                                        bstadd(Value,Left,Rez) ,
                                        X = [Key,Rez,Right]
                                      ; %else (Value > Key)
                                        % then add to right side
                                        bstadd(Value,Right,Rez) ,
                                        X = [Key,Left,Rez]
                                    ).

Upvotes: 2

Related Questions