Pseudocode to compare two trees

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.

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.

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);
}

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.