Recursive calls with match for operation search on binary tree

Question

I have come across a solution to the problem of searching a value in the binary tree and returning the node of that residing value. The time complexity is thus expected to be O(n).

This is my solution to the problem:

let rec search x tree = 
  match tree with 
  | Empty -> Empty
  | Node (root, left, right) when x = root -> tree
  | Node (_, left, right) ->
    match left with
    | Empty -> search x right
    | t -> search x t

and this is the solution I found, but I think mine is more efficient and readable:

let rec search x t =
  match t with
  | Empty -> Empty
  | Node(v, l, r) ->
    if v = x then t
    else 
      match search x l with
      | Empty -> search x r
      | t' -> t'

Is my solution better or am I missing something?

For reference, the definition of the tree type:

type 'a tree = 
  | Empty
  | Node of 'a * 'a tree * 'a tree

Answer 1

These are not equivalent in functionality.

Your function only searches the right branch if the left branch is itself Empty, and not if the result of searching that branch is Empty.

Consider:

# let leaf v = Node (v, Empty, Empty) in
  search 4 @@ Node (2, leaf 1, leaf 4);;
- : int tree = Empty

You might have meant:

let rec search x tree = 
  match tree with 
  | Empty -> Empty
  | Node (root, _, _) when x = root -> tree
  | Node (_, left, right) ->
    match search x left with
    | Empty -> search x right
    | t -> t

Now:

# let leaf v = Node (v, Empty, Empty) in
  search 4 @@ Node (2, leaf 1, leaf 4);;
- : int tree = Node (4, Empty, Empty)

An additional thought is that you may want to create a search_opt function which returns an option type, where None indicates that no match was found.

let rec search_opt x = 
  function 
  | Empty -> None
  | Node (root, _, _) as tree when x = root -> Some tree
  | Node (_, left, right) ->
    match search_opt x left with
    | None -> search_opt x right
    | t -> t

Let's say we have a tree: let t = Node (2, Node (5, Node (7, leaf 1, leaf 6), leaf 10), Node (8, leaf 3, leaf 4).

          ------2------
         /             \
     ---5---         ---8---
    /       \       /       \
  -7-       10     3         4
 /   \
1     6

If I evaluate search_opt 3 t, then that breaks down something like:

search_opt 3 t
  search_opt 3 (Node (5, Node (7, leaf 1, leaf 6), leaf 10))
    search_opt 3 (Node (7, leaf 1, leaf 6))
      search_opt 3 (Node (1, Empty, Empty))
        search_opt 3 Empty -> None
        search_opt 3 Empty -> None
    search_opt 3 (Node (10, Empty, Empty))
      search_opt 3 Empty -> None
      search_opt 3 Empty -> None
  search_opt 3 (Node (8, leaf 3, leaf 4))
    search_opt 3 (Node (3, Empty, Empty)) -> Some (Node (3, Empty, Empty))