6 Replies - 6729 Views - Last Post: 29 September 2015 - 09:34 AM

#1 ishkabible   User is offline

  • spelling expret
  • member icon





Reputation: 1747
  • View blog
  • Posts: 5,898
  • Joined: 03-August 09

Challenge: Tree Isomorphism

Post icon  Posted 15 September 2015 - 08:42 AM

So one of the more recent threads in CS was discussing issues with logarithms and big-oh notation. A little while back I found an interesting problem involving logarithms. I figured it was time for a good old classic, write an algorithm problem anyhow too.

Two trees (we will only binary trees) are isomorphic if you can perform some number of swaps between left and right siblings to achieve the same tree.

So for instance the following trees are isomorphic

          
          1
         / \
       /     \
     2       5
    /\
   3  4

          1
         / \
       /     \
     5       2
             / \
            3   4


but the flowing are not

          
          1
         / \
       /     \
     2       5
    /\
   3  4

          1
         / \
       /     \
     2       5
             / \
            3   4


Your challenge is to write an algorithm that checks to see if two trees are isomorphic and then explain what the running time is and why. You may either consider balanced binary trees or unbalanced binary trees. You shouldn't need to consider balanced trees however but it allows for a different argument if you have that assumption.

There is a natural solution to this problem that looks something like the following (in spoiler tags so you can come up with your own).

Spoiler


My immediate thought was that this algorithm was very very slow. I thought it had exponential running time. Why does it not have exponential running time? Also tell my what your intuitions were when you first saw this problem (be it here or elsewhere). Mine personally were wrong but depending on how you look at this it could actually be very obvious. Which camp were you in?

This post has been edited by ishkabible: 15 September 2015 - 08:43 AM


Is This A Good Question/Topic? 2
  • +

Replies To: Challenge: Tree Isomorphism

#2 KYA   User is offline

  • Wubba lubba dub dub!
  • member icon

Reputation: 3207
  • View blog
  • Posts: 19,239
  • Joined: 14-September 07

Re: Challenge: Tree Isomorphism

Posted 15 September 2015 - 02:06 PM

My initial gut reaction is that this can be done in linear time.

Spoiler


Perhaps I'm missing something?

This post has been edited by KYA: 15 September 2015 - 02:12 PM

Was This Post Helpful? 0
  • +
  • -

#3 mojo666   User is offline

  • D.I.C Addict
  • member icon

Reputation: 409
  • View blog
  • Posts: 885
  • Joined: 27-June 09

Re: Challenge: Tree Isomorphism

Posted 15 September 2015 - 03:47 PM

This is my first time seeing this and my gut reaction was that it could be done linearly, but I was assuming unique values.

Spoiler

Was This Post Helpful? 1
  • +
  • -

#4 ishkabible   User is offline

  • spelling expret
  • member icon





Reputation: 1747
  • View blog
  • Posts: 5,898
  • Joined: 03-August 09

Re: Challenge: Tree Isomorphism

Posted 15 September 2015 - 05:57 PM

KYA: mind elaborating? I don't think I understand your how you are constructing this tuple list

mojo66: What depth first pattern? I can think of a few things that might mean. It sounds similar to my solution but I am not sure exactly what you are saying here.

Your second solution is really neat! I love the answer. There is however a linear algorithm that works even for non-unique values (I wrote it in Haskell in spoiler tags if you want to see).
Was This Post Helpful? 0
  • +
  • -

#5 mojo666   User is offline

  • D.I.C Addict
  • member icon

Reputation: 409
  • View blog
  • Posts: 885
  • Joined: 27-June 09

Re: Challenge: Tree Isomorphism

Posted 21 September 2015 - 09:44 AM

Quote

What depth first pattern?


Spoiler

Was This Post Helpful? 2
  • +
  • -

#6 KYA   User is offline

  • Wubba lubba dub dub!
  • member icon

Reputation: 3207
  • View blog
  • Posts: 19,239
  • Joined: 14-September 07

Re: Challenge: Tree Isomorphism

Posted 27 September 2015 - 03:01 PM

edit: Just noticed that this is essentially the DFS pattern mojo posted in the above comment that I hadn't spoilered yet. Oh well.

I'm late, but here is an implementation using my BinarySearchTree.

Rather than build up tuples, just check by going down...

Spoiler


The tuple thing looks something like this: http://www.cs.upc.ed...aph-00-01-c.pdf pages 4-6

This post has been edited by ishkabible: 28 September 2015 - 09:35 PM

Was This Post Helpful? 2
  • +
  • -

#7 mojo666   User is offline

  • D.I.C Addict
  • member icon

Reputation: 409
  • View blog
  • Posts: 885
  • Joined: 27-June 09

Re: Challenge: Tree Isomorphism

Posted 29 September 2015 - 09:34 AM

Quote

edit: Just noticed that this is essentially the DFS pattern mojo posted in the above comment that I hadn't spoilered yet. Oh well.


Actually, I made a mistake in the main logic. My code returns false positives if one tree has a symmetric portion and the other tree has a match for the symmetric half. Your logic is correct.

I'm still not sure how to make this thing linear, though.
Was This Post Helpful? 0
  • +
  • -

Page 1 of 1