Finding a better solution for comparing binary trees

Question

Here's a type for binary trees

type tree =
  | Node of tree * int * tree
  | Null;;

and I've got a following problem to solve:

Write a function tree -> tree -> int that returns a number which says for how many levels down (going from the root) the trees are essentialy the same (same values at nodes and same shapes). Here's a 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 I'm really dissatisfied with this code - it's really hard to understand, even for me. What I'm doing is essentially on every level of the tree I'm creating a list for left and right tree containing all subtrees on corresponding levels (and also whether the subtree is left or right son for determining the shape) and then comparing this list on every level. If they are identical I increment the result, if not - I return the result.

But when I use this "algorithm" I end up with this complicated code. So could it be done simplier?

You don't need to put parens in many places where you have pair expressions. Try removing some (unless it seems more readable to you?) — didierc
– didierc, Commented Nov 20, 2014 at 3:22
I heard that when putting functions in a pair, not putting parenthesess can lead to unexpected results (like OCaml thinking I want to compute the function now, not pass it as an element of the pair). That's the reason I'm always using parenthesses. — qiubit
– qiubit, Commented Nov 20, 2014 at 9:28
Sorry, I understand that you want to make sure the compiler will not misunderstand your intent. Basically, the comma has a low precedence in Ocaml grammar, but it turns out to be fairly OK in many cases, and avoiding them leads to lighter code (as you surely know). I suppose it's matter of taste, or maybe habit. Many people tend to avoid unnecessary parentheses, so if you read a lot of other's code, you'll probably get used to it. — didierc
– didierc, Commented Nov 20, 2014 at 11:09
Btw, I was mainly thinking about pattern matchings, when pairs are not a parameter of a Constructor. — didierc
– didierc, Commented Nov 20, 2014 at 11:11

Pierre G. · Accepted Answer · 2014-11-18 20:25:40Z

2

I would like to propose 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 tests patterns :

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 the level 1 (int 1) is the same in both trees, but but on level 2, the subtrees that are on the rights differ (2 vs 3). The second test returns 2 since the head is the same, and the 2 subtrees have same value, what differs next is the additionnal subtree. Is it the correct expected behaviour ?

answered Nov 18, 2014 at 20:25

Pierre G.

4,4631 gold badge15 silver badges28 bronze badges

Sign up to request clarification or add additional context in comments.

1 Comment

qiubit Over a year ago

Yes, tests are correct. Thanks for your code, that's exactly what I wanted my solution to look like.

stark · Accepted Answer · 2014-11-18 18:51:24Z

2

A better algorithm is just to do a standard depth-first search. Stop and back up when you either a) find a difference, or b) hit the depth where you have already found a difference in a previous branch.

answered Nov 18, 2014 at 18:51

stark

13.3k3 gold badges39 silver badges56 bronze badges

Collectives™ on Stack Overflow

Finding a better solution for comparing binary trees

2 Answers 2

1 Comment

Comments

Your Answer

Hot Network Questions

Collectives™ on Stack Overflow

2 Answers 2

1 Comment

Comments

Your Answer

Sign up or log in

Post as a guest

Related