Tree

SPOILER: this article assumes quite a lot of things about your knowledge of binary trees and data structure. I won’t spend much time introducing concepts. Deal with it. Some time ago I had the pleasure to meet with Chris Lord, who introduced me to the concept of Binary Tree Traversal without using neither a stack/queue or recursion. The list of requirements that such algorithm has to fulfil: Constant Space: no extra data structure to do the traversal Non-destructive: once finished, the tree needs to be exactly how it was before the visit Sounded crazy initially, but than I looked into it more deeply and discovered, thanks to some pointers from Luca Colantonio, that there is an algorithm in literature that does just that: Morris In-Order Traversal. ...

My granma always used to say every time she was recompiling the Linux Kernel of her wash machine: Bash Scripting is GREAT! Be sure you learn it. One day will understand why it can make your life much easier. And she was right! I’m not an Bash expert, but when I spend that 10 minutes putting together that scripts that _makes that tedious task piece of cake, the satisfaction is as tick as a Mug of Coffee. ...

Imagine you have a Binary Tree, with those characteristics: * Nodes do not respect any order relation - In other words: it's <strong>not</strong> a [Binary Search Tree](http://en.wikipedia.org/wiki/Binary_search_tree) of any kind * Every node appears <em>once and only once</em> within the tree A nice Binary Tree Then, your little brother passes by your desk and, to upset you, deletes the tree from your computer memory/HD (yeah, I know, I’m pathetic at inventing hypothetical situations :-P ). Fortunately though, you previously did a Pre-Order and an In-Order visit of your tree, and stored the result in an 2 nice array. Can you rebuild the original tree structure out of this 2 array? How are you going to rebuild it? Yes, you can! (Sorry, I couldn't resist). And it's quite easy as well. What you have to do, is the following: Take the first element of the PreOrder Array and use it as root of a new tree Find the position of this New Node in the InOrder Array, scanning it from 0 to n-1 (n is the number of Nodes) IF next element in the PreOrder Array is on the left of the New Node in the InOrder array: call RECURSIVELY this procedure, this time taking into account the portion of InOrder array that goes from 0 to the position of the New Node in the InOrder Array -1. IF next element in the PreOrder Array is on the right of the New Node in the InOrder array: call RECURSIVELY this procedure, this time taking into account the portion of InOrder array that goes from the position of the New Node in the InOrder Array +1 to n-1. Return the New Node By the way, this doesn’t work. To fix it we should be more generic, specifying things a little bit better. Things like: * Every recursive calls takes into account a portion of the InOrder array; in the case of the first call it's the entire array * There is going to be as much recursive calls as the number of elements in the PreOrder array Of course, is a tree what we are talking about here: recursion is a MUST. ...