Pseudocode to compare two trees

Question

This is a problem I've encountered a few times, and haven't been convinced that I've used the most efficient logic.

As an example, presume I have two trees: one is a folder structure, the other is an in-memory 'model' of that folder structure. I wish to compare the two trees, and produce a list of nodes that are present in one tree and not the other - and vice versa.

Is there an accepted algorithm to handle this?

Gretta

To who-ever down-voted the issue. I'd be grateful if you'd give some feedback why the down-vote, then I can get a better Stack Overflow participant... – Gretta

Answer 1

Seems like you just want to do a pre-order traversal, essentially. Where "visiting" a node means checking for children that are in one version but not the other.

More precisely: start at the root. At each node, get a set of items in each of the two versions of the node. The symmetric difference of the two sets contains the items in one but not the other. Print/output those. The intersection contains the items that are common to both. For each item in the intersection (I assume you aren't going to look further into the items that are missing from one tree), call "visit" recursively on that node to check its contents. It's a O(n) operation, with a little recursion overhead.

Alis

Note: the traversal is O(n). Symmetric difference and intersection depend on the container you are using to store the items, whether they are sorted, etc. – Alis

Answer 2

public boolean compareTrees(TreeNode root1, TreeNode root2) {
  if ((root1 == null && root2 != null) || 
      (root1 != null && root2 == null)) {
    return false;
  }

  if (root1 == null && root2 == null) {
    return true;
  }

  if (root1.data != root2.data) {
    return false;
  }

  return compareTrees(root1.left, root2.left) && 
    compareTrees(root1.right, root2.right);
}

Antonio

Answer 3

A simple example code in python.

class Node(object):
    def __init__(self, val):
        self.val = val
        self.child = {}
    
    def get_left(self):
        # if left is not in the child dictionary that means the element does not have a left child
        if 'left' in self.child:
            return self.child['left']
        else:
            return None
    
    def get_right(self):
        # if right is not in the child dictionary that means the element does not have a right child
        if 'right' in self.child:
            return self.child['right']
        else:
            return None

    def traverse_tree(a):
        if a is not None:
            print 'current_node : %s' % a.val
        if 'left' in a.child:
            traverse_tree(a.child['left'])
    
        if 'right' in a.child:
            traverse_tree(a.child['right'])
    
    def compare_tree(a, b):
        if (a is not None and b is None) or (a is None and b is not None):
            return 0
        elif a is not None and b is not None:
            print a.val, b.val
        
        # print 'currently comparing a : %s, b : %s, left : %s, %s , right : %s, %s' % (a.val, b.val, a.child['left'].val, b.child['left'].val, a.child['right'].val, b.child['right'].val)
        if a.val==b.val and compare_tree(a.get_left(), b.get_left()) and compare_tree(a.get_right(), b.get_right()):
            return 1
        else:
            return 0
        else:
            return 1


# Example

a = Node(1)
b = Node(0)
    
a.child['left'] = Node(2)
a.child['right'] = Node(3)
a.child['left'].child['left'] = Node(4)
a.child['left'].child['right'] = Node(5)
a.child['right'].child['left'] = Node(6)
a.child['right'].child['right'] = Node(7)
b.child['left'] = Node(2)
b.child['right'] = Node(3)
b.child['left'].child['left'] = Node(4)
#b.child['left'].child['right'] = Node(5)
b.child['right'].child['left'] = Node(6)
b.child['right'].child['right'] = Node(7)

if compare_tree(a, b):
    print 'trees are equal'
else:
    print 'trees are unequal'

# DFS traversal
traverse_tree(a)

Also pasted an example that you can run.

Dower

Answer 4

If you use a sort tree, like an AVL tree, you can also traverse your tree efficiently in-order. That will return your paths in sorted order from "low" to "high". Then you can sort your directory array (e.g. Using quicksort) using the same compare method as you use in your tree algorithm.

Then start comparing the two side by side, advancing to the next item by traversing your tree in-order and checking the next item in your sorted directory array.

This should be more efficient in practice, but only benchmarking can tell.

Vaughnvaught

Answer 5

You may also want to have a look at how git does it. Essentially whenever you do a git diff, under the hood a tree comparison is done.

Iquitos