Subscribe to Stuck in an Infiniteloop

## An Isomorphic Exercise with Old Code

Has anyone looked at code they wrote six months ago and went...what was I thinking?

Today I went to some code I wrote in 2009. That's right, 2009. This interesting challenge was presented in the computer science forum.

How can we tell if two binary trees are isomorphic? Two trees are isomorphic if they differ only sibling swaps.

So I grab the binary search tree code and throw on the isomorphic check:

```template<class T>
bool BinarySearchTree<T>::isIsomorphic(BinarySearchTree<T>* one, BinarySearchTree<T>* two){
return isIsomorphic(one->root, two->root);
}

template<class T>
bool BinarySearchTree<T>::isIsomorphic(Node<T>* one, Node<T>* two){
if (one == NULL && two == NULL) return true;
if (one == NULL || two == NULL) return false;
if (one->getData() != two->getData()) return false;

return ( (isIsomorphic(one->getLeftChild(), two->getLeftChild()) && isIsomorphic(one->getRightChild(), two->getRightChild())) ||
(isIsomorphic(one->getLeftChild(), two->getRightChild()) && isIsomorphic(one->getRightChild(), two->getLeftChild()))
);
}

```

The above snippet is a depth first search on the tree. In the first part of the boolean expression, it checks to see if the left and right subtrees are the same. If they are, the trees are isomorphic. If any point one node is NULL or the data doesn't match, the trees are not isomorphic. If that is not conclusive, we then "flip" the check and see if any subtree is mirrored.

Running time: O(m+n) where m is the number of nodes in tree one and n is the number of nodes in tree two. As pointed out in that thread, this solution is only linear for unique values in the trees.

-------------------------------------------

Oh man it compiles! Does it work???

```#include <iostream>
#include <string>
#include "BinarySearchTree.h"
using namespace std;

int main(){
BinarySearchTree<int>* tree = new BinarySearchTree<int>(6);

BinarySearchTree<int>* tree2 = new BinarySearchTree<int>(6);
tree2->addNode(4); //comment this out for true eval below

cout << BinarySearchTree<int>::isIsomorphic(tree, tree2) << endl; //false
delete tree;
delete tree2;
return 0;
}

```

Excellent, it all works. So either that code held up extremely well or it was simple enough to not really rot over the years.

In any event, this has led me to consolidate the data structure code from this blog over the years into a single git repo: https://github.com/T...data-structures

Each contains the source at the time of writing (mmmm maybe there are some bugs that could almost be in Kindergarten) and a sample driver. That's some good nostalgia right there.

### 2 Comments On This Entry

Page 1 of 1

#### ishkabible

28 September 2015 - 10:26 PM
Glad you liked the challenge! I love it when I get to use old code of mine. I pretty much always end up rewriting it somehow though. I always have a better idea.
0

#### WolfCoder

13 October 2015 - 10:45 AM
I'm always rewriting code if its for real stuff (not assignments, etc.) because of constantly changing requirements, or i need to increase performance, etc. When I do that, I always make sure there's much fewer lines of code in the project than when I started.

I'm reminded of that one sarcastic software engineer who had to report the lines of code they've written in a report for their (misinformed) supervisor, so he would always write a negative number there.
0
Page 1 of 1

S M T W T F S
12 3 45
6789101112
13141516171819
20212223242526
2728293031