// Something like this: public boolean treesEqual(NodePair roots) { Stack stack = new Stack(); stack.push(roots); while(!stack.isEmpty()) { NodePair nodes = stack.pop(); Node left = nodes.left(); Node right = nodes.right(); if(!nodesEqual(left, right)) return false; if(left != null && right != null) { stack.push(new NodePair(left.left(), right.left())); stack.push(new NodePair(left.right(), right.right())); } } return true; }

Another solution can be is, first check that the lengths and the roots are same for both the BST's and if they are, then do Inorder traversal to check if both are same. If all three conditions (same root, height and inorder then same BST's). If either root or height dont match then dont do inorder and return it as false.

Think of both trees as a heap representation (without heap properties), where the index of the root is 1, and index of a left child is (2 x index of its parent), and index of a right child is (1+ index of left child). Then traverse one tree in BFS fashion, at each node, do a BS on the second tree. If found, compare their indices. The index can be calculated on the fly during traversing and BS, so you don't really need to copy the tree to an array or something. This is just a theory in my head. I haven't really written code to prove it works.

The code by Java Dev will fail if one tree is bigger than the other and they are identical for all the elements in the small tree.

Recursive implementation was presented. Was asked to do non-recursive version (question was not about better solution, say, w/constant memory) – I proposed to change recursive algorithm to non-recursive with a user-defined stack (formal transformation rather boring but doable, FORTRAN people do it). Demonstrated that but code was messy with gotos, etc. Asked about complexity – both recursive and non-recursive versions required linear stack in worst case of pathological one-sided trees.