CODEWITHSUNDEEP
searchhaskelltreefindbinary-tree
ciembor
ciembor

Reputation: 7335

Finding element in a binary tree

Assume I have a binary tree:

data Bst a = Empty | Node (Bst a) a (Bst a)

I have to write a function that searches for a value and returns the number of its children. If there is no node with this value, it returns -1. I was trying to write both BFS and DFS, and I failed with both.

Upvotes: 0

Views: 1872

Answers (2)

Paul
Paul

Reputation: 8182

Here is a way to do this. Breath-first search can actually be a bit tricky to implement and this solution (findBFS) has aweful complexity (appending to the list is O(n)) but you'll get the gist.

First I have decided to split out the finding functions to return the tree where the node element matches. That simplifies splitting out the counting function. Also, it is easier to return the number of elements than the number of descendants and return -1 in case not found, so the numDesc functions rely on the numElements function.

data Tree a = Empty
            | Node a (Tree a) (Tree a)

numElements :: Tree a -> Int
numElements Empty        = 0
numElements (Node _ l r) = 1 + numElements l + numElements r

findDFS :: Eq a => a -> Tree a -> Tree a
findDFS _ Empty                         = Empty
findDFS x node@(Node y l r) | x == y    = node
                            | otherwise = case findDFS x l of 
                                            node'@(Node _ _ _) -> node'
                                            Empty              -> findDFS x r

findBFS :: Eq a => a -> [Tree a] -> Tree a                                                                
findBFS x []                              = Empty
findBFS x ((Empty):ts)                    = findBFS x ts
findBFS x (node@(Node y _ _):ts) | x == y = node
findBFS x ((Node _ l r):ts)               = findBFS x (ts ++ [l,r])

numDescDFS :: Eq a => a -> Tree a -> Int
numDescDFS x t = numElements (findDFS x t) - 1

numDescBFS :: Eq a => a -> Tree a -> Int
numDescBFS x t = numElements (findBFS x [t]) - 1

Upvotes: 1

Greg Bacon
Greg Bacon

Reputation: 139711

Pattern matching is your friend. Your Bst can either be Empty or a Node, so at the toplevel, your search function will be

search Empty = ...
search (Node left x right) = ...

Can an Empty tree possibly contain the target value? With a Node the target value, if present, will be either the node value (x above), in the left subtree, in the right subtree—or perhaps some combination of these.

By “return[ing] the number of its children,” I assume you mean the total number of descendants of the Bst rooted at a Node whose value is the target, which is an interesting combination of problems. You will want another function, say numChildren, whose definition uses pattern matching as above. Considerations:

  1. How many descendants does an Empty tree have?
  2. In the Node case, x doesn’t count because you want descendants. If only you had a function to count the number of children in the left and right subtrees …

Upvotes: 2

Related Questions