Space/Time complexity of Binary Tree Equality

Question

I had an interview yesterday that involved a pretty basic tree data structure:

t ::= int | (t * t)

where a tTree is either an integer (leaf) or two t's which represent left and right subtrees. This implies that the tree will only have values at the leaf level.

An example tree could look like this:

         t 
      /     \ 
     t        t
   /   \    /   \
  1     2  3     4

The task was to write a function equal(t, t) => bool that takes two tTrees and determines whether or not they are equal, pretty simple.

I wrote pretty standard code that turned out like this (below is pseudocode):

fun equal(a, b) {
   if a == b {   // same memory address
      return true
   } 

   if !a || !b { 
      return false
   }

   // both leaves 
   if isLeaf(a) && isLeaf(b) {
      return a == b 
   }

   // both tTrees
   if isTree(a) && isTree(b) {
      return equal(a->leftTree, b->leftTree) 
          && equal(a->rightTree, b->rightTree)
   }

   // otherwise
   return false
}

When asked to give the time and space complexity, I quickly answered:

O(n) time 
O(1) space

My interviewer claimed they could create a tree such that this equal function would run in O(2^n) exponential time. I didn't (and still don't) see how this is possible given the algorithm above. I see that the function recursively calls itself twice, but the input size is halved on each of those calls right? because you are only examining the respective subtrees in parallel.

Any thoughts or input on this would be really helpful.

Answer 1

As it stands, your code is O(n), and your interviewer was mistaken. The code's not O(1) in space use though: it's O(n) in the worst case (when the trees are very unbalanced) because your code is recursive (and not tail recursive).

Probably they were asking you to write a function that tests if two trees are isomorphic. That is, they were expecting you to write code that returns true when comparing these two trees:

  *      *
 / \    / \
1   2  2   1

Then they misread your solution, assuming you'd written the naive code that does this, which would be O(2^n).

Another possibility is that some of the pointers could be reused in both the left and right branches of the same tree, allowing a tree with 2^n nodes to be represented in O(n) space. Then if 'n' is the size of the structure in memory, rather than the number of nodes, then the interviewer's position is correct. Here's such a tree:

  ___   ___   ___   ___   ___
 /   \ /   \ /   \ /   \ /   \
*     *     *     *     *     1
 \___/ \___/ \___/ \___/ \___/

The root is on the left, and it has 32 leaf nodes (all 1).