CODEWITHSUNDEEP
ctreebinary-treetree-traversalpostorder
fresh42juice
fresh42juice

Reputation: 117

How can I construct a strict binary tree when the only information given is post order traversal?

Previously I asked how to get the pre-order of a tree when I am only given post-order traversal. However, now I'm curious as to how one would build a strict binary tree (strict binary tree meaning a node either has two children or no children) when only given post order traversal. Some example data I am dealing with :

7 8 2 // 8,2 are dimensions stored in the node, likewise for other nodes)
6 4 8
3 1 5
A
B

I know what the tree is supposed to look like:

               B
            /     \
           7       A
                 /    \
                6      3

But I am lost on how to write a function that would actually build this tree (and store in the information in the nodes) from the information given (post order traveral.) How can I do this?

Upvotes: 1

Views: 580

Answers (1)

M Oehm
M Oehm

Reputation: 29116

Creating a full binary tree from the postorder is like creating a syntax tree from Reverse Polish Notation with only binary operators. The branches are the operators, the leaves are the values. (You must be able to tell which is which. In your axample, brenches are letters, leaves are numbers.)

You can process the data as it comes. If it is a leaf, create a node and push it on the stack. It is is a branch, create a node, pop its right and left branches off the stack and push the new node. If the received data is valid, you should have a single node on the stack. That's the root of your tree.

So, in pseudo-ish C code:

Node *head = NULL;

while (!stream_empty()) {
    int data = stream_get();

    if (is_leaf(data)) {
        if (nstack == MAX) fatal("Stack overflow!");

        stack_push(make_node(data));
    } else {
        if (stack_size < 2) fatal("Stack underflow!");

        Node *node = make_node(data);

        node->right = stack_pop();
        node->left = stack_pop();
        stack_push(node);
    }
}

if (nstack != 1) fatal("Ill-formed full binary tree!");

head = stack[0];

Stack overflow occurs when the tree is deeper than the stack size. Stack underflow or leftover nodes at the end occur when the input data is ill-formed.

Here's a full working example on ideone.

[Note: I've completely rewritten my answer, because the OP has specified new requirements. I had also based my original answer of a answer I gave to OP's previous question. I think that the present approach is more elegant. Whatever that means. :)]

Upvotes: 2

Related Questions