#include <stdio.h>
// Recursive function to find postorder traversal of binary tree
// from its inorder and preorder sequence
void printPostorder(int inorder[], int start, int end,
int preorder[], int *preIndex)
{
// base case
if (start > end)
return;
// The next element in preorder[] will be the root node of subtree formed
// by inorder[start, end]
int value = preorder[(*preIndex)++];
// if current node is leaf node (no children)
if (start == end)
{
// print the value of root node and return
return;
}
// search the index of root node in inorder[] to determine the
// boundary of left and right subtree of current root node
int i;
for (i = start; i <= end; i++) {
if (inorder[i] == value)
break;
}
// recur for left subtree
printPostorder(inorder, start, i - 1, preorder, preIndex);
// recur for right subtree
printPostorder(inorder, i + 1, end, preorder, preIndex);
// print the value of root node
}
// Find postorder traversal of a binary tree from its inorder and
// preorder sequence. This function assumes that the input is valid
// i.e. given inorder and preorder sequence forms a binary tree
void findPostorder(int inorder[], int preorder[], int n)
{
// preIndex stores index of next unprocessed node in preorder sequence
int *preIndex;
// root node is present at index 0 in preorder sequence
preIndex = 0;
printf("Postorder Traversal is: "); printPostorder(inorder, 0, n - 1, preorder, &preIndex);
}
// main function
int main(void)
{
/* Consider below tree
1
/ \
/ \
2 3
/ / \
/ / \
4 5 6
/ \
/ \
7 8
*/
int inorder[] = { 4, 2, 1, 7, 5, 8, 3, 6 };
int preorder[] = { 1, 2, 4, 3, 5, 7, 8, 6 };
int n = sizeof(inorder)/sizeof(inorder[0]);
findPostorder(inorder, preorder, n);
return 0;
}
I2luY2x1ZGUgPHN0ZGlvLmg+CgovLyBSZWN1cnNpdmUgZnVuY3Rpb24gdG8gZmluZCBwb3N0b3JkZXIgdHJhdmVyc2FsIG9mIGJpbmFyeSB0cmVlCi8vIGZyb20gaXRzIGlub3JkZXIgYW5kIHByZW9yZGVyIHNlcXVlbmNlCnZvaWQgcHJpbnRQb3N0b3JkZXIoaW50IGlub3JkZXJbXSwgaW50IHN0YXJ0LCBpbnQgZW5kLCAKICAgICAgICAgICAgICAgICAgICBpbnQgcHJlb3JkZXJbXSwgaW50ICpwcmVJbmRleCkKewogICAgLy8gYmFzZSBjYXNlCiAgICBpZiAoc3RhcnQgPiBlbmQpCiAgICAgICAgcmV0dXJuOwoKICAgIC8vIFRoZSBuZXh0IGVsZW1lbnQgaW4gcHJlb3JkZXJbXSB3aWxsIGJlIHRoZSByb290IG5vZGUgb2Ygc3VidHJlZSBmb3JtZWQKICAgIC8vIGJ5IGlub3JkZXJbc3RhcnQsIGVuZF0KICAgIGludCB2YWx1ZSA9IHByZW9yZGVyWygqcHJlSW5kZXgpKytdOwoKICAgIC8vIGlmIGN1cnJlbnQgbm9kZSBpcyBsZWFmIG5vZGUgKG5vIGNoaWxkcmVuKQogICAgaWYgKHN0YXJ0ID09IGVuZCkKICAgIHsKICAgICAgICAvLyBwcmludCB0aGUgdmFsdWUgb2Ygcm9vdCBub2RlIGFuZCByZXR1cm4KICAgICAgICBwcmludGYoIiVkICIsIHZhbHVlKTsKICAgICAgICByZXR1cm47CiAgICB9CgogICAgLy8gc2VhcmNoIHRoZSBpbmRleCBvZiByb290IG5vZGUgaW4gaW5vcmRlcltdIHRvIGRldGVybWluZSB0aGUKICAgIC8vIGJvdW5kYXJ5IG9mIGxlZnQgYW5kIHJpZ2h0IHN1YnRyZWUgb2YgY3VycmVudCByb290IG5vZGUKICAgIGludCBpOwogICAgZm9yIChpID0gc3RhcnQ7IGkgPD0gZW5kOyBpKyspIHsKICAgICAgICBpZiAoaW5vcmRlcltpXSA9PSB2YWx1ZSkKICAgICAgICAgICAgYnJlYWs7CiAgICB9CgogICAgLy8gcmVjdXIgZm9yIGxlZnQgc3VidHJlZQogICAgcHJpbnRQb3N0b3JkZXIoaW5vcmRlciwgc3RhcnQsIGkgLSAxLCBwcmVvcmRlciwgcHJlSW5kZXgpOwoKICAgIC8vIHJlY3VyIGZvciByaWdodCBzdWJ0cmVlCiAgICBwcmludFBvc3RvcmRlcihpbm9yZGVyLCBpICsgMSwgZW5kLCBwcmVvcmRlciwgcHJlSW5kZXgpOwoKICAgIC8vIHByaW50IHRoZSB2YWx1ZSBvZiByb290IG5vZGUKICAgIHByaW50ZigiJWQgIiwgdmFsdWUpOwp9CgovLyBGaW5kIHBvc3RvcmRlciB0cmF2ZXJzYWwgb2YgYSBiaW5hcnkgdHJlZSBmcm9tIGl0cyBpbm9yZGVyIGFuZCAKLy8gcHJlb3JkZXIgc2VxdWVuY2UuIFRoaXMgZnVuY3Rpb24gYXNzdW1lcyB0aGF0IHRoZSBpbnB1dCBpcyB2YWxpZAovLyBpLmUuIGdpdmVuIGlub3JkZXIgYW5kIHByZW9yZGVyIHNlcXVlbmNlIGZvcm1zIGEgYmluYXJ5IHRyZWUKdm9pZCBmaW5kUG9zdG9yZGVyKGludCBpbm9yZGVyW10sIGludCBwcmVvcmRlcltdLCBpbnQgbikKewogICAgLy8gcHJlSW5kZXggc3RvcmVzIGluZGV4IG9mIG5leHQgdW5wcm9jZXNzZWQgbm9kZSBpbiBwcmVvcmRlciBzZXF1ZW5jZQogICAgaW50ICpwcmVJbmRleDsKCiAgICAvLyByb290IG5vZGUgaXMgcHJlc2VudCBhdCBpbmRleCAwIGluIHByZW9yZGVyIHNlcXVlbmNlCiAgICBwcmVJbmRleCA9IDA7CgogICAgcHJpbnRmKCJQb3N0b3JkZXIgVHJhdmVyc2FsIGlzOiAiKTsKICAgIHByaW50UG9zdG9yZGVyKGlub3JkZXIsIDAsIG4gLSAxLCBwcmVvcmRlciwgJnByZUluZGV4KTsKfQoKLy8gbWFpbiBmdW5jdGlvbgppbnQgbWFpbih2b2lkKQp7CiAgICAvKiBDb25zaWRlciBiZWxvdyB0cmVlCiAgICAgICAgICAxCiAgICAgICAgLyAgIFwKICAgICAgIC8gICAgIFwKICAgICAgMiAgICAgICAzCiAgICAgLyAgICAgICAvIFwKICAgIC8gICAgICAgLyAgIFwKICAgNCAgICAgICA1ICAgICA2CiAgICAgICAgICAvIFwKICAgICAgICAgLyAgIFwKICAgICAgICA3ICAgICA4CiAgICAqLwogICAgCiAgICBpbnQgaW5vcmRlcltdICA9IHsgNCwgMiwgMSwgNywgNSwgOCwgMywgNiB9OwogICAgaW50IHByZW9yZGVyW10gPSB7IDEsIDIsIDQsIDMsIDUsIDcsIDgsIDYgfTsKICAgIGludCBuID0gc2l6ZW9mKGlub3JkZXIpL3NpemVvZihpbm9yZGVyWzBdKTsKCiAgICBmaW5kUG9zdG9yZGVyKGlub3JkZXIsIHByZW9yZGVyLCBuKTsKCiAgICByZXR1cm4gMDsKfQ==