Finding the best solution for comparing binary trees
Here's the type for binary trees
type tree =
| Node of tree * int * tree
| Null;;
and I got the following problem:
Write a function tree -> tree -> int
that returns a number that tells you how many levels down (comes from the root) trees are important the same (same values in nodes and same shapes). Here is the solution I wrote:
let rec identical l1 l2 =
match (l1, l2) with
| ([], []) -> true
| ((tree1, s1) :: t1, (tree2, s2) :: t2) ->
if s1 = s2 then
match (tree1, tree2) with
| (Null, Null) -> identical t1 t2
| (_, Null) -> false
| (Null, _) -> false
| (Node (l1, x1, r1), Node (l2, x2, r2)) ->
if x1 = x2 then identical t1 t2
else false
else false;;
let unfold l =
let l = List.filter (fun (a, b) ->
if a = Null then false else true) l in
if List.length l = 0 then raise Nulls else
List.fold_left (fun acc (a, b) ->
match a with
| Node (l, x, r) ->
(l, "l") :: (r, "r") :: acc) [] l;;
let compare t1 t2 =
let rec aux l1 l2 result =
if (List.length l1 <> List.length l2)
then result
else
if (identical l1 l2) then
try
aux (unfold l1) (unfold l2) (result + 1)
with
| Nulls -> result
else
result
in aux [(t1, "r")] [(t2, "r")] 0;;
The problem is that I am really unhappy with this code - it is very difficult to understand, even for me. What I am doing is essentially at each level of the tree, I create a list for the left and right trees, containing all the subtrees at the respective levels (as well as whether the subtree is left or right to determine the shape), and then comparing that list to every level. If they are identical, I increment the result, if not, I return the result.
But when I use this "algorithm" I get this complex code. So can this be done easier?
source to share
I would like to suggest the following code:
let rec compare_tree t1 t2 =
match (t1, t2) with
| (Null, Null) | (Null, _ ) | ( _ , Null ) -> 0
| (Node (t1_l, x, t1_r), Node (t2_l, y, t2_r)) ->
if x=y then
1 + min
(compare_tree t1_l t2_l)
(compare_tree t1_r t2_r)
else 0;;
Two test templates:
let t1 = Node (Node (Null,1,Null),1,Node (Null, 2, Null));;
let t2 = Node (Node (Null,1,Null),1,Node (Null, 3, Null));;
let c = compare_tree t1 t2 in
Printf.printf "compare = %d\n" c
;;
let t1 = Node (Node (Null,1,Null),1,Node (Null, 2, Null));;
let t2 = Node (Node (Null,1,Null),1,Node (Node (Null,1,Null), 2, Null));;
let c = compare_tree t1 t2 in
Printf.printf "compare = %d\n" c
;;
The first test returns 1: only level 1 (int 1) is the same in both trees, but, but at level 2, the subtrees on the rights are different (2 versus 3). The second test returns 2 since the head is the same, and the 2 subtrees have the same value, and the other is an additional subtree. Is this the correct expected behavior?
source to share