Algorithm Problem #2: Unordered Tree Equality

Problem Statement

Given a following class describing binary tree type Tree and assuming that particular type K will extend Comparable.

Add some Lombok magic for less boilerplate code.

import lombok.*;

@NoArgsConstructor
@AllArgsConstructor
@Getter
@Setter
@ToString
public interface Tree<K> {
    K key();
    Tree<K> left();
    Tree<K> right();
}

Implement an equality check between Tree instances that will return true when:

• key is equal between T1 and T2
• Subtrees are equal but without regard for ordering

Other info:

• DO NOT modify input Tree
• Assume that key is non null

Breakdown

1. Input will be two instances of Tree interface, and we need to return boolean value.

2. Next thing is considering possible variants when trees will be equal. It will be one of two possibilites:

   • T1.left == T2.left AND T1.right == T2.right
   • T1.left == T2.right AND T1.right == T2.left

3. It’s possible to just recursively check for possibilities, but it has a problem with performance which will be exponential O(2^N) where N is tree size

4. To solve this ambiguity Comparable property of type K can be used. Instead of checking recursively both possible variant just create ordering on the fly and always compare trees with smaller key and trees with larger key respectively.

Implementation Consideration

Question remains what’s the cleanest/nicest way of structuring solution?

Possible options are:

1. Override equals
   Create a concrete implementation of interface and override equals method. But this has many problems:

   • This kind of equality isn’t very intuitive, so it’s potentially very error prone
   • We would be restricted only to this concrete implementation instead of being able to do this kind of comparison on any class implementing Tree interface

2. Implement Comparable
   Same issues as above plus:

   • No obvious way to indicate one instance as larger than another, this again creates non-intuitive behavior and potential problems

3. Implement Comparator
   Fixes issue of being tied to particular implementation of Tree, but still has issues with ordering of inputs that will be not equal.

4. Implement static method
   This solves all above problems and is nicely self-contained. Only issue is that it will be kind of a utility class which usually introduces maintenance problems.

5. Implement BiPredicate That seems like the way to go with problem at hand.

   • It’s returning boolean so no issues of ordering unequal input
   • Not tied to particular implementation of Tree
   • Follows Java functional conventions, making it ready usable in standard library frameworks

Solution

Start with class declaration that will include BiPredicate and extends Comparable on generic type T. Declare method required by functional interface.

public class UnorderedTreeEquality<T extends Comparable<T>> implements BiPredicate<Tree<T>, Tree<T>> {

   @Override
   public boolean test(Tree<T> first, Tree<T> second) {
      return false;
   }
}

Now handle edge cases for possible null input trees and not equal key values

if (first == null && second == null) {
   return true;
} else if (first == null || second == null) {
   return false;
}

if (!first.key().equals(second.key())) {
   return false;
}

If execution passes past those conditions then following things are true:

• Both first and second are not null
• Their keys are equal

So now we have to move to comparing subtrees. First we’ll need to establish that both subtrees are not null to actually attempt key comparison. In the event that left.key < right.key. Also in case only one subtree is not null assume that comparison order is left, right, and reverse otherwise. Last thing code for second input tree will be completely analogous.

   // This would go into else clauses, so assume it as a default
   Tree<T> firstSmaller = first.right();
   Tree<T> firstBigger = first.left();
   
   if (first.left() != null && first.right() != null) {
      if (first.left().key().compareTo(first.right().key()) < 0) {
          firstSmaller = first.left();
          firstBigger = first.right();
      }
   } else if (first.left() != null) {
      firstSmaller = first.left();
      firstBigger = first.right();
   }

Last step is to perform recursive calls on subtrees.

return test(firstSmaller, secondSmaller) && test(firstBigger, secondBigger);

Complexity Analysis

• N is the size (number of nodes) in smaller input Tree

TIME: Each node in smaller Tree is visited once and null leaves are visited once, which gives us O(N)

MEMORY: Longest possible recursion chain will occur for degenerate case of “LinkedList” Tree, which will result in allocating additional O(N) call stack frames.

Complete Implementation and Tests

• Implementation: UnorderedTreeEquality.java
• Tests: Implementing property based testing on this code requires generation of random unary-binary trees and will be covered in a follow-up notes.