Well the "brain-brush" series continues. One of my favourite binary tree question would be given a preorder and inorder traversal strings write a function to build the tree. Most of the rubbish text books provide non-programmatic solution to this and rest append it as a to-do. Today I will proceed step-by-step to solve this and that too with same ingredients - delegate, generics and C#2.0. Disclaimer still holds: "This is just a fundamental recapitulation of binary tree and data structure as a whole. Geeks excuse me please for this series.
In the earlier post I discussed the simple data structure of treenode and binary tree. Just to repeat once following is the skeleton of my binary tree class
public class BinaryTree
{
//root node
public TreeNode root;
//Algorithms...InOrder etc.
}
Now for simplicity lets assume that the binary treenode contains single character data. So instead of embedding our tree-building algo inside this generic BinaryTree class I specialized ot to create a subclass called CharBinaryTree. Lets construct the base logic Assume we have following binary tree -
Preorder traversal string and Inorder traversal strings are 124536 and 425163 respectively Lets now back calculate and see how one might can possibly build the tree. Firstly preorder string always helps to get the root right. VLR. Does it ring a bell? But then how to differntiate between left subtree(LT) and right subtree(RT). Well simple. Split the inorder string based on the pivotal root. Left substring is LT and right substring is RT. Now we have to recurse. That's fine. But what are the pivotal indexes for LT and RT. Simple - if you can see dry-run the first recursion frame
root := 1, LT := 425, RT := 63
pivot(LT) := pivot+1, pivot(RT) := pivot + len(LT) + 1.
Naturally these pivotal characters will be the roots of the respective subtrees. Enough said. Let's dump the C# code right now.
private TreeNode MakeTree(string inorderString, int preOrderIndex)
{
TreeNode p = new TreeNode(' ');
// terminating condition
if (inorderString.Length == 1)
{
char.TryParse(inorderString, out p.nodeData);
}
else
{
char pivot = this.preorderString[preOrderIndex];
int rootIndexInorder = inorderString.IndexOf(pivot);
string left = "";
string right = "";
if (rootIndexInorder > 0)
{
left = inorderString.Substring(0, rootIndexInorder);
right = inorderString.Substring(rootIndexInorder + 1);
p.nodeData = pivot;
if (left.Length != 0)
p.left = MakeTree(left, preOrderIndex + 1);
if (right.Length != 0)
p.right = MakeTree(right, preOrderIndex + left.Length + 1);
}
}
return p;
}
This goes the private "workhorse" function as described in my earlier post of the DS-BrainBrush series. Lets see the driver function
public TreeNode MakeTree(string inorderString, string preorderString)
{
//Couple of pre-checks
if ((inorderString.Length == 0) ||
(preorderString.Length == 0))
{
throw new ArgumentException("Traversal strings shouldn't be empty");
}
if (inorderString.Length != preorderString.Length)
{
throw new ArgumentException("Traversal strings should have identical length");
}
//Make a copy of traversal strings
this.preorderString = preorderString;
this.inorderString = inorderString;
//Make a call to "workhorse"
this.root = this.MakeTree(this.inorderString, 0);
return this.root;
}
Everything fits nicely in the "workhorse-driver" model. In the next post of this series I will show how to create a special binary tree called Binary Expression Tree(BET) heavily used in world of lexical analyzer, parser and compilers. See you soon.