CODEWITHSUNDEEP
haskellrecursiontree
Aditya Subramanian
Aditya Subramanian

Reputation: 87

Subtrees of Binary Trees in a range Haskell

I have a Binary Tree defined as the following:

data BSTree = Void | BSNode BSTree Integer BSTree

and would like to write a function

subTree:: Integer -> Integer -> BSTree -> BSTree

which returns all subset of trees with a <= key < b.

I tried the following

subTree:: Integer -> Integer -> BSTree -> BSTree
subTree a b Void = Void
subTree a b (BSNode leftTree key rightTree) 
    | key < a = BSNode Void key (subTree key b rightTree)
    | b < key = BSNode (subTree a key leftTree) key Void
    | a <= key && b > key = BSNode (subTree a key leftTree) key (subTree key b rightTree)

but do not get the correct output. Could someone point out the flaw in my logic?

Upvotes: 2

Views: 260

Answers (1)

developer_hatch
developer_hatch

Reputation: 16224

I each step of the recursion, you should provide a and b arguments:

data BSTree = Void | BSNode BSTree Integer BSTree deriving Show

subTree:: Integer -> Integer -> BSTree -> BSTree
subTree a b Void = Void
subTree a b (BSNode leftTree key rightTree) 
 | key < a = --your logic here
 | b < key = -- your logic here
 | a <= key && b > key = BSNode (subTree a b leftTree) key (subTree a b rightTree)

t1 = BSNode Void 5 Void
t2 = BSNode Void 6 Void
t3 = BSNode Void 7 Void
t4 = BSNode t1 8 (BSNode t1 7 t2)

With this example:

   subTree 6 10 t4
=> BSNode Void 8 (BSNode Void 7 (BSNode Void 6 Void))

Upvotes: 2

Related Questions