javarecursiontreetraversalpostorder

How to traverse a list in postorder manner which was made in preorder?

In java I have a list where each element consist of a leftName and rightName. If the left or rightName is null it indicates that it has an another leaf/node (if both of them are null they have 2 leaves). The list was made from a tree in preorder traversal, and now I would like to go through the the elements in postorder manner.

Other from the null-s you can not really know the order of the list by looking at the text. (In the case of ordered numbers it would be much easier).

Example for the list: [[null,null],[something1,something2],[otherthing1,otherthing2]]

Desired output

something1,something2,otherthing1,otherthing2

Another example for the list: [[something,null],[other,secondOther],[otherthing1,otherthing2]]

Desired output

something, other, secondother, otherthing1, otherthing2

I have managed to correctly traverse through the whole left side of the list, but finding the index of the last element in the left side is hard for me. (If you know this number dynamically you can process the right side of the tree).

Thanks for the help in advance!

Solution

  • You write:

    now I would like to go through the the elements in postorder manner

    If you don't intend to include the null items, then it wouldn't make any difference if you went through the elements in pre-order, in-order or post-order manner: the output will be the same.

    The binary tree you describe is a full binary tree with no data in the internal nodes. The difference between traversal orders like pre-order, in-order and post-order, is when internal nodes are visited:

    But this does not affect the relative order in which they visit leaf nodes, because they all visit a node's left child before its right child! The order of the leaf visits is the same for all three traversals.

    Example

    Your example was a bit small, so here is a less trivial example, where I have temporarily labeled the internal nodes with numbers:

                                 _______1______ 
                            /              \
                         __2__              6
                        /     \            / \
                       3       5          7   I
                      / \     / \        / \
                     A   4   D   E      8   H
                        / \            / \
                       B   C          F   G

    Here are the traversals for this tree:

    Pre-order:  1 2 3 A 4 B C 5 D E 6 7 8 F G H I
In-order:   A 3 B 4 C 2 D 5 E 1 F 8 G 7 H 6 I
Post-order: A B C 4 3 D E 5 2 F G 8 H 7 I 6 1

    If we now remove the labels of the internal nodes, and just keep the data, we see all these traversals have the same order for that data:

    Pre-order:  A B C D E F G H I
In-order:   A B C D E F G H I
Post-order: A B C D E F G H I

    Algorithm

    The algorithm to make the traversal can use recursion or an explicit stack. I went with the second option. Here I have defined the data as strings, but it would be similar for any other data type:

        static List<String> collectLeaves(String[][] tree) {
        List<String> output = new ArrayList<>();
        Stack<String> stack = new Stack<>();
        stack.push(null);
        for (var pair : tree) {
            stack.push(pair[1]);
            stack.push(pair[0]);
            while (stack.peek() != null) {
                output.add(stack.pop()); // data
            }
            stack.pop(); // null
        }
        return output;
    }

    And here is some code to define the example as input and use the above function:

            String[][] input = {
            {null, null}, {null, null}, {"A", null}, {"B", "C"},
            {"D", "E"}, {null, "I"}, {null, "H"}, {"F", "G"},
        };
        var output = collectLeaves(input);
        for (var item : output) {
            System.out.print(item + " ");
        }
        System.out.println();

    Output:

    A B C D E F G H I