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);

	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:

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


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.


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.
Page 1 of 1

April 2019

21 22 2324252627


    Recent Entries

    Recent Comments

    Search My Blog

    1 user(s) viewing

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