Subscribe to Stuck in an Infiniteloop        RSS Feed
-----

An Isomorphic Exercise with Old Code

Icon 2 Comments
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);
	tree->addNode(10);
	tree->addNode(3);

	BinarySearchTree<int>* tree2 = new BinarySearchTree<int>(6);
	tree2->addNode(10);
	tree2->addNode(3);
	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

April 2019

S M T W T F S
 123456
78910111213
14151617181920
21 22 2324252627
282930    

Tags

    Recent Entries

    Recent Comments

    Search My Blog

    1 user(s) viewing

    1 Guests
    0 member(s)
    0 anonymous member(s)