Hi Shashank,
Please find below the psuedocode for constructing the Binary tree from pre
and post order traversal.
My assumption was that given pre and post order traversal of a tree, binary
tree can be constructed of any form. Correct me if I am wrong..
Lets assume the pre and post order traversals of the tree are stored in an
array.
Pre order traversal: Pre[1..n]
Post order traversal: Post[1..n]
where n is the # of nodes in the tree.
root: empty for the new binary tree..
For simplicity, leaving the linear search traversal and creating node,
handling ptrs.. in tree construction
// Check whether ith node in post order array is before jth node in post
order array.
// Returns true if ith node is before jth node in post order array, else
false.
// where i and j are indices in the pre-order tree
bool is_child_node(int i, int j) {
k = array index of of pre[i] in post order tree (linear search in post
order tree)
l = array index of pre[j] in post order tree (linear search in post order
tree)
return (k <= l)
}
int add_node_to_tree(parent, child) {
if (!parent) return -1;
// add as left child if no children..
if (!parent->left)
parent->left = child;
else if (!parent->right)
parent->right = child;
else
print ("DEBUG: parent already has 2 children.. cannot add extra
node..");
return 0;
}
// Traverse the pre-order tree linearly. Make a note of its predecessors in
the same tree.
// Search for the array index position of the current entry and the
predecessor in the post-order tree.
// If the current entry index is before the predecessor index in the post
order tree,
// the predeccesor is parent of current entry index. Else, go to next
predecessor.
int create_bin_tree_from_pre_post_order(pre, post, n) {
if (!n) print("pre and post order lists are empty.."; return -1;
//for simplicity: array indices start from 1.
root = create_node(pre[1]);
for (int i = 2; i <=n; i++) {
create_node(pre[i]);
for (int j = i-1; j >= 0; j--) { // j goes to 0 to handle the
error...
if (!j) print ("ERROR: failed to find pre[i] root in the tree"),
return -1;
if (is_child_node(i, j) {
parent = pre[j], child = pre[i];
add_node_to_tree(parent, child);
break;
}
}
}
// Traverse from root to display the constructed tree..
return 0;
}
This psuedocode is cursory and written naively in hurry. There might be
obvious bugs. Let me know.
Thanks,
Balaji
On Tue, Feb 1, 2011 at 10:55 AM, bittu <shashank7andr...@gmail.com> wrote:
> Given a Special BT in which Each Non Leaf Node Except Root Has at-
> least two children .Given Pre-order and Post-order of Tree Your Task
> is to design the tree From the Given Information..
>
>
> Thanks & Regards
> Shashank Mani
>
> --
> You received this message because you are subscribed to the Google Groups
> "Algorithm Geeks" group.
> To post to this group, send email to algogeeks@googlegroups.com.
> To unsubscribe from this group, send email to
> algogeeks+unsubscr...@googlegroups.com<algogeeks%2bunsubscr...@googlegroups.com>
> .
> For more options, visit this group at
> http://groups.google.com/group/algogeeks?hl=en.
>
>
--
You received this message because you are subscribed to the Google Groups
"Algorithm Geeks" group.
To post to this group, send email to algogeeks@googlegroups.com.
To unsubscribe from this group, send email to
algogeeks+unsubscr...@googlegroups.com.
For more options, visit this group at
http://groups.google.com/group/algogeeks?hl=en.
