Small BST solver for contest at work. I think I cheated.

wtreef

// Submitted by: Brandon Perry
// wtreef.cpp : Defines the entry point for the console application.
//

//Quick run:
/*
brandon.perry@BRANPERRY-X64 ~
$ time '/cygdrive/c/Users/brandon.perry/Documents/Visual Studio 2013/Projects/wtreef/Release/wtreef.exe'
Created a valid binary tree, but invalid BST. The tree was fixed and verified for 10 nodes.
Created a valid binary tree, but invalid BST. The tree was fixed and verified for 2010 nodes.
Created a valid binary tree, but invalid BST. The tree was fixed and verified for 4010 nodes.
Created a valid binary tree, but invalid BST. The tree was fixed and verified for 6010 nodes.
Created a valid binary tree, but invalid BST. The tree was fixed and verified for 8010 nodes.
Created a valid binary tree, but invalid BST. The tree was fixed and verified for 10010 nodes.
Created a valid binary tree, but invalid BST. The tree was fixed and verified for 12010 nodes.
Created a valid binary tree, but invalid BST. The tree was fixed and verified for 14010 nodes.
Created a valid binary tree, but invalid BST. The tree was fixed and verified for 16010 nodes.
Created a valid binary tree, but invalid BST. The tree was fixed and verified for 18010 nodes.
Created a valid binary tree, but invalid BST. The tree was fixed and verified for 20010 nodes.
Created a valid binary tree, but invalid BST. The tree was fixed and verified for 22010 nodes.
Created a valid binary tree, but invalid BST. The tree was fixed and verified for 24010 nodes.
Created a valid binary tree, but invalid BST. The tree was fixed and verified for 26010 nodes.
Created a valid binary tree, but invalid BST. The tree was fixed and verified for 28010 nodes.

real    0m0.237s
user    0m0.015s
sys     0m0.124s

brandon.perry@BRANPERRY-X64 ~
$
*/


#include "stdafx.h"//required for windows

//These are needed for linux compilation
#include <limits.h> 
#include <stdio.h> 
#include <stdlib.h> 
#include <iostream>
#include <functional>

//The m_data private member is two pointers
//away from the beginning of the class in memory.
//Two pointers on 32-bit is 8 bytes, 16 bytes on 64-bit (or sizeof(intptr_t)*2),
//so even without a SetData method, we can still set the value :)
class Tree
{
private:
	Tree* m_pLeft;
	Tree* m_pRight;
	unsigned int m_data;
	unsigned int m_scratchPad;
public:
	Tree(unsigned int aData) : m_pLeft(NULL), m_pRight(NULL), m_scratchPad(0){ m_data = aData; }
	Tree* GetLeft() const { return m_pLeft; }
	void SetLeft(Tree* apLeft) { m_pLeft = apLeft; }
	Tree* GetRight() const { return m_pRight; }
	void SetRight(Tree* apRight) { m_pRight = apRight; }
	unsigned int GetData() const { return m_data; }
	unsigned int GetScratchPad() const { return m_scratchPad; }
	void SetScratchPad(unsigned int aScratchPad) { m_scratchPad = aScratchPad; }
};

// The only method that matters
void FixTree(Tree* apTree);

//These are for testing and verification only
Tree* CreateTree(unsigned int i);
bool VerifyTree(Tree* tree);
bool IsBST(Tree* tree, unsigned int min, unsigned int max);

int main(int argc, char* argv[]) {
	for (int i = 10; i < 30000; i += 2000){ 
		Tree* tree = CreateTree(i);
		if (VerifyTree(tree)){
			printf("Created an already valid BST, skipping...\n");
			continue;
		}
		else
		{
			printf("Created a valid binary tree, but invalid BST. ");
		}
		FixTree(tree);
		printf("The tree was%sfixed and verified for %d nodes.\n", (VerifyTree(tree) ? " " : " not "), i);
	}
	return 0;
}

void FixTree(Tree* apTree) {
	if (apTree == NULL)
		return;

	unsigned int count = 0;
	//allocate to heap to save stack space for recursion
	unsigned int *vals = new unsigned int[50000];
	Tree* current = apTree;
	Tree* pre = NULL;

	//this is a morris traversal algorithm
	//traverse the tree iteratively to get node count
	do
	{
		if (current->GetLeft() == NULL){
			current = current->GetRight();
		}
		else
		{
			*(vals + count) = current->GetLeft()->GetData();
			pre = current->GetLeft();
			while (pre->GetRight() != NULL && pre->GetRight()->GetData() != current->GetData())
				pre = pre->GetRight();

			if (pre->GetRight() == NULL)
			{
				*(vals + count) = current->GetLeft()->GetData();
				count++;
				pre->SetRight(current);
				current = current->GetLeft();
			}
			else
			{
				*(vals + count) = current->GetRight()->GetData();
				count++;
				pre->SetRight(NULL);
				current = current->GetRight();
			}

		}
	} while (current != NULL);

	unsigned int *realvals = new unsigned int[count];

	for (int i = 0; i < count; i++)
		*(realvals + i) = *(vals + i);

	qsort(realvals, count, sizeof(int), [](const void * x, const void * y) { return (*(int*)x - *(int*)y); });

	count = 0;
	unsigned int *p;

	//let's party, who needs a SetData method? this might be cheating...
	std::function<void(unsigned int*, Tree*, unsigned int*)> BST = [&BST,&p](unsigned int* vals, Tree* node, unsigned int* i){
		if (node == NULL)
			return;

		BST(vals, node->GetLeft(), i);

		//m_data is intptr_t*2 bytes away from the beginning of the node in memory
		//just create a pointer to m_data by hand and reassign the value :P
		p = (unsigned int*)((intptr_t)node + sizeof(intptr_t) * 2);
		*p = *(vals + *i);
		(*i)++;

		BST(vals, node->GetRight(), i);
	};

	BST(realvals, apTree, &count);

	delete[] realvals;
}

bool VerifyTree(Tree* tree) {
	return IsBST(tree, 0, UINT_MAX);
}

//Create a tree where:
//You are guaranteed that all the m_data values are unique,
//that there is one node in the tree per data value,
//and that all data nodes are reachable from the root node.
Tree* CreateTree(unsigned int size) {
	Tree* tree = new Tree(1);

	Tree* cur = tree;
	for (int i = 2; i <size; i += 2) {
		
		cur->SetLeft(new Tree(i+1));
		cur->SetRight(new Tree(i));

		cur = cur->GetRight()->GetData() % 2 == 0 ? cur->GetLeft() : cur->GetRight();
	}

	return tree;
}

bool IsBST(Tree* tree, unsigned int min, unsigned int max)
{
	if (tree == NULL)
		return true;

	if (tree->GetData() < min || tree->GetData() > max)
		return false;

	return
		IsBST(tree->GetLeft(), min, tree->GetData() - 1) && 
		IsBST(tree->GetRight(), tree->GetData() + 1, max);  
}