PostOrder traversal of binary tree jumps inconsistently to either sibling or parent

Question

When entering the following values ({18, 26, 52, 78, 45, 16, 67, 58, 73, 11}) in a Binary Tree , you receive this tree:

Both PreOrder and InOrder traversals work as I expect them to. However, when it comes to PostOrder (PO) I'm receiving something different than I would've thought.

As I understand it, PO first searches trough the left subtree, then then the right subtree and eventually the node (ending in the root node).

When traversing in PO trough this tree, you end up with the following result: {11, 16, 45, 58, 73, 67, 78, 52, 26, 18}. When writing out the logic behind this result, you get the following: Starting at the root, following full left you end up in 11 which is your first node. After that you go up one level and take its parent (16). You continue doing this untill you reach the root (which doesn't get included because it isn't a leftChild). Once you've been trough this initial left subtree, you go a level down at the right and check for leftChilds there. If there aren't any, you go down another level which is where we find 45.

At this point we have a list of {11, 16, 45}. We continue this and end up in 58 which is our next value in the result. This is where my confusion comes in: the next value we get is 73, contrary to the expected 67. Why did it jump to 73 when there is another leftChild to be found (its parent)?

The following code takes care of traversing trough the tree in PostOrder:

public void postorderTraversal(){
    postorderHelper(root);
}

private void postorderHelper(Node node){
    if(node != null){
        postorderHelper(node.getLeftNode());
        postorderHelper(node.getRightNode());
        System.out.print(node.getData() + " ");
    }
}

I'm guessing this is because the node with value 73 is processed before the parentNode (left-right-top priority), but why isn't this the case in the 45-52-78 triangle then?

Answer 1

I'm guessing this is because the node with value 73 is processed before the parentNode (left-right-top priority), but why isn't this the case in the 45-52-78 triangle then?

It is, in that 45 comes before 78, which comes before 52.

A left sibling will always be visited before a right sibling, which will always be visited before a parent. What else is visited between those will depend on what children the left and right siblings have.

The wikipedia page on tree traversal describes it as:

To traverse a non-empty binary tree in postorder, perform the following operations recursively at each node:

• Traverse the left subtree.
• Traverse the right subtree.
• Visit the root.

So you'll only ever visit a node if you've visited all its children, and you'll always visit a left subtree before a right subtree. Everything in your results goes along with this.