# Progress on Inverting a Binary Search Tree

My days are currently in a rhythm where they start in the afternoon, but on the day I decided to revisit my binary search tree inversion problem, my day began at 09:00. As such, I wanted to be productive and make use of my unpexpected time, so I decided to spend a few hours trying to come up with an algorithm that works.

I projected that such a decision to work on the problem would be optimal as I believed that it didnâ€™t require as much energy as working on something like planning the architecture of a video game or a web app. Indeed, the project only involved sovling one specific problem, that of inverting a binary search tree. I initially thought that being able to solve such a problem would not have required much knowledge or awareness, but Iâ€™m now beginning to think that I jumped to a conclusion.

# The algorithm

The algorithm that I have right now, in psuedocode:

``````allNodes = []
allNodes.push(tree.rootNode)
currentNode = tree.rootNode
parentNode = null
traversingLeft = true
numberOfNodesTraversed = 0
while (numberOfNodesTraversed != tree.numberOfNodes):
if (traversingLeft AND currentNode.leftNode):
allNodes.push(currentNode.leftNode)
numberOfNodesTraversed++
parentNode = currentNode
currentNode = currentNode.leftNode
else if (currentNode.rightNode):
allNodes.push(currentNode.rightNode)
numberOfNodesTraversed++
traversingLeft = true
parentNode = currentNode
currentNode = currentNode.rightNode
else:
traversingLeft = false
currentNode = parentNode

for (i = 0; i < allNodes.length; i++):
Simply exchange the left and right nodes
``````

The most recent change I made to the algorithim was to use the information obtained from a counter that gets incremented everytime a new node is inserted, thereby giving the total number of nodes in the binary search tree. This practice of having available such a feature may or may not be an optimal solution as it could be costly in the context of a large scale architecture. Believing that, I didnâ€™t want to do it that way. I instead wanted to only rely on using the information provided by the nodes themselves rather than installing a new member `numberOfNodes` onto the `BinarySearchTree` class, which is the implemention of the binary search tree thatâ€™s operated on.

One issue with this algorithm (and why it doesnâ€™t work) is that previous parent nodes are not getting re-traversed, because they are not being tracked in some sort of collection. One idea Iâ€™m currently implementing is using a collection (which has already been implemented with the addition of traversed nodes to the `allNodes` array) and computing offsets to jump back up to previous parent nodes.

Sometimes it feels like Iâ€™m over-engineering the solution and that thereâ€™s a simple solution that involves some knowledge that I donâ€™t have.

# Still questing for the answer

Iâ€™ve spent two months trying to solve this problem, mostly because of other things vying for my attention and time. During the course of these two months, though, I did try to come up with solutions while I wasnâ€™t in front of the code. I even developed somewhat of a fascination or obsession with binary search trees.

I am tempted, at times, to look up the answer to inverting a binary search tree. But maybe I like being teased, enthralled by the longing for the divine knowledge of this advanced concept. I can see this sort of thing turning into a labor of love.

September 18, 2017