Hi,
if you have an in-order traversal and a post-order traversal for a general binary tree, they don't even define the tree uniquely if you can have duplicated values, e.g. the sequence [1,1,1] for both post-order and in-order can be one of the following trees:
1 1
1 1 1
1
And the minimum-sum path has sum of 2 on the left and the sum of 3 on the right.
So assume all the values are distinct.
Suppose you have a post-order traversal list [x1,x2,...,xn] and in-order traversal list [y1,...,yk,...,yn] so that xn==yk. Because xn is the root of the tree, you know now that [y1,...,yk-1] is the left subtree and [yk+1,...,yn] is the right subtree. The left subtree is then also represented by [x1,...,xk-1] because the size of the left subtree is obviously constant, so you can divide the post-order traversal list also between xk-1 and xk.
As an example, here is a non-balanced binary tree without any specific ordering:
5
3 6
9 2 1
4
The in-order traversal is [9,3,2,5,6,4,1] and the post-order [9,2,3,4,1,6,5].
The tree would be recursively constructed like this: Take last element of post-order traversal (5); divide in-order to [9,3,2] and [6,4,1] (dividing at the location of the element 5); thus the post-order traversal list is split to [9,2,3] and [4,1,6] just based on the now-known sizes of the subtrees. The recursion then continues; let's look at the [6,4,1] tree because it is not balanced:
The root is 6; in the in-order [6,4,1] the left-subtree is empty and the right is [4,1], so from the post-order list [4,1,6] you take [] as the left-subtree and [4,1] as the right subtree; from there you get root-node 1, and you find that [4] is the left subtree; from which you get the shape
6
1
4
as desired.
Now because your tree is not ordered, balanced, etc., you could just try to write recursive code to handle your query. Here it is in C++:
const int size = 7; /* Size of the tree */
/* Given arrays */
int post_order[size] = { 3 , 1 , 2 , 5 , 6 , 7 , 4 };
int in_order[size] = { 3 , 2 , 1 , 4 , 5 , 7 , 6 };
/* Variables updated during recursion */
int min_sum = 99999999; /* not initialized */
int best_leaf = -1; /* not initialized */
/* Recursive descent */
/* prb = post-order range begin, irb = in-order range begin, etc. */
void min_sum_leaf(int acc, int prb, int irb, int len) {
if (len == 0) return; /* empty subtree */
if (len == 1) { /* leaf */
int sum = acc + in_order[irb];
if (sum<min_sum) { min_sum = sum; best_leaf = in_order[irb]; }
return;
}
/* non-leaf */
int subtree_root = post_order[prb + len - 1];
/* find the size of the left subtree */
int i;
for (i=0;i<len;i++) {
if (in_order[irb + i] == subtree_root) break;
}
/* Now i is the length of the left subtree, len - i - 1 of the right */
min_sum_leaf(acc + subtree_root, prb, irb, i);
min_sum_leaf(acc + subtree_root, prb + i, irb + i + 1, len - i - 1);
}
/* Driver */
int find_min_sum_leaf() {
min_sum = 99999999; best_leaf = -1;
min_sum_leaf(0, 0, 0, size);
return best_leaf;
}
Note: I haven't compiled or run the algorithm but the logic should be there!