Binary Tree Postorder Traversal

/**
 * Definition for binary tree node structure.
 * struct TreeNode {
 *     int value;
 *     TreeNode *leftChild;
 *     TreeNode *rightChild;
 *     TreeNode(int x) : value(x), leftChild(NULL), rightChild(NULL) {}
 * };
 */
class Solution {
public:
    vector<int> traversePostorder(TreeNode* root) {
        vector<int> output;

        if (root == NULL) {
            return output;
        }

        TreeNode dummyNode(-1);
        TreeNode* tempNode = &dummyNode;
        TreeNode* prev = NULL;
        tempNode->leftChild = root;
        root = tempNode;

        while (root != NULL) {
            if (root->leftChild != NULL) {
                prev = root->leftChild;

                while (prev->rightChild != NULL && prev->rightChild != root) {
                    prev = prev->rightChild;
                }

                if (prev->rightChild == NULL) {
                    prev->rightChild = root;
                    root = root->leftChild;
                } else {
                    TreeNode* iterNode = prev;
                    reverseLinks(root->leftChild, prev);

                    while (iterNode != root->leftChild) {
                        output.push_back(iterNode->value);
                        iterNode = iterNode->rightChild;
                    }

                    output.push_back(iterNode->value);
                    reverseLinks(prev, root->leftChild);
                    prev->rightChild = NULL;
                    root = root->rightChild;
                }
            } else {
                root = root->rightChild;
            }
        }

        return output;
    }

    void reverseLinks(TreeNode* start, TreeNode* end) {
        if (start == end) return;

        TreeNode* previous = NULL;
        TreeNode* current = start;
        TreeNode* next = NULL;

        while (current != end) {
            next = current->rightChild;
            current->rightChild = previous;
            previous = current;
            current = next;
        }

        current->rightChild = previous;
    }
};

This C++ solution implements a postorder traversal of a binary tree. It involves traversing the tree's nodes in the sequence of left child, right child, and then the node itself. The implementation leverages the Morris traversal technique, which is iterative and does not require additional memory for recursion or a stack.

The traversePostorder function begins by checking if the root node is NULL and, if so, returns an empty vector. It then introduces a dummy node to simplify edge case handling by connecting it initially to the root. Throughout the traversal, the algorithm uses a temporary pointer and a previous pointer to help manage and modify tree connections dynamically, avoiding recursion overhead.

The core of the algorithm lies in its ability to temporarily modify the tree structure without using additional space:

• It first makes a connection between the end of a subtree's rightmost node back to the current root if it is not already set. This backlink helps in navigating back to the root after finishing the subtree.
• After completing the left subtree, the algorithm reverses the links of the nodes to record the values from the rightmost to the current node. This is crucial as it simulates the stack pop operation seen in standard postorder traversal using recursion or iteration with explicit stacks.

The reverseLinks function serves the purpose of in-place link reversal between the specified start and end nodes. This function facilitates the correct order of node processing. It employs the classic technique of reversing a linked list applied here to the right child pointers of the tree nodes.

Once the traversal is complete, the algorithm restores the original tree structure and continues until all nodes are processed. By ensuring that each non-null node and its children are correctly managed and then reversing the temporary modifications, this approach efficiently simulates a postorder traversal without additional memory usage typically incurred using stacks or recursion.

class BinaryTree {

    public List<Integer> postOrderTraversal(TreeNode node) {
        List<Integer> nodesList = new ArrayList<>();

        if (node == null) {
            return nodesList;
        }

        TreeNode tempNode = new TreeNode(-1);
        TreeNode lastNode = null;
        tempNode.left = node;
        node = tempNode;

        while (node != null) {
            if (node.left != null) {
                lastNode = node.left;

                while (lastNode.right != null && lastNode.right != node) {
                    lastNode = lastNode.right;
                }

                if (lastNode.right == null) {
                    lastNode.right = node;
                    node = node.left;
                } else {
                    TreeNode temp = lastNode;
                    reverseLinks(node.left, lastNode);

                    while (temp != node.left) {
                        nodesList.add(temp.val);
                        temp = temp.right;
                    }
                    nodesList.add(temp.val);
                    reverseLinks(lastNode, node.left);
                    lastNode.right = null;
                    node = node.right;
                }
            } else {
                node = node.right;
            }
        }

        return nodesList;
    }

    private void reverseLinks(TreeNode fromNode, TreeNode toNode) {
        if (fromNode == toNode) {
            return;
        }

        TreeNode prev = null;
        TreeNode current = fromNode;
        TreeNode next;

        while (current != toNode) {
            next = current.right;
            current.right = prev;
            prev = current;
            current = next;
        }
        current.right = prev;
    }
}

This document details how to perform a postorder traversal on a binary tree using Java without recursion, focusing on the Morris traversal technique to achieve the desired output.

First, initialize a temporary node pointing to the root. This approach uses a dummy node with its left child as the actual root of the tree to handle edge cases seamlessly.

Implement while loops to process each node in the binary tree:

1. If the current node has a left child, find the rightmost child in its left subtree, which does not already link back to the current node.
2. If this rightmost node does not point back to the current node, create a temporary link back to the current node, then move to the left child of the current node. If it does link back, it indicates the subtree has been visited, so the temporary link is removed, and the subtree values are collected in reverse order.
3. If the current node does not have a left child, move directly to its right child.

To conveniently process and store node values in postorder during the traversal:

1. Reverse the links starting from the left child of the current node up to the rightmost node to collect the values.
2. After collecting values, reverse the links back to restore the original structure of the tree.

The utility function reverseLinks efficiently reverses the links between specified nodes, facilitating the sequential addition of node values to the list in postorder.

Finally, return the list of node values, which gives a complete postorder traversal of the binary tree. This implementation provides an in-depth usage of manipulation of binary tree pointers to achieve postorder traversal without recursion or stack, ensuring efficiency in both time and space complexity.

class Solution:
    def postorder(self, root):
        output = []

        if not root:
            return output

        temp_root = TreeNode(-1)
        temp_root.left = root
        root = temp_root

        while root:
            if root.left:
                previous = root.left

                while previous.right and previous.right != root:
                    previous = previous.right

                if previous.right == None:
                    previous.right = root
                    root = root.left
                else:
                    walker = previous
                    self._reverse_nodes(root.left, previous)

                    while walker != root.left:
                        output.append(walker.val)
                        walker = walker.right
                    output.append(walker.val)
                    self._reverse_nodes(previous, root.left)
                    previous.right = None
                    root = root.right
            else:
                root = root.right

        return output

    def _reverse_nodes(self, start, end):
        if start == end:
            return

        prev = None
        current = start
        next_node = None

        while current != end:
            next_node = current.right
            current.right = prev
            prev = current
            current = next_node
        current.right = prev

In this solution summary for the binary tree postorder traversal using Python, the approach employs an iterative method instead of recursion, making it a bit more complex but efficient for certain use cases. Postorder traversal entails visiting left subtree, right subtree, and finally the node itself.

• Initialize an empty list output to store the traversal result.
• A dummy node temp_root with a value of -1 is created to handle edge cases smoothly by setting its left child as the input root.
• Begin with temp_root as your starting root.
• Use a while loop to navigate through the tree. If the current node (root in this case) has a left child, find the rightmost node of this left subtree (unless this rightmost node points back to the current node, indicating a loop structure due to previous modifications).
• If the rightmost node (previous in this code) doesn't point anywhere, make it point back to root, and then move root to its left child, ensuring traversal happens for the entire left subtree.
• If the rightmost node points back to root, it indicates a previously visited state. Here, reverse the nodes from the left child of root to previous, allowing a modification in traversal order to collect values in postorder. The function _reverse_nodes helps in reversing these nodes.
• Move through the reversed nodes, gather values in output, restore the original tree structure using _reverse_nodes again, and continue the traversal for the right subtree.
• If no left child exists, straightforwardly move to the right child.
• Continue this loop until root is exhausted.
• Return the output, which now contains the postorder traversal of the binary tree.

The auxiliary function _reverse_nodes in the class aids in reversing the links between a start node and an end node in the tree. This reversal is crucial for temporarily modifying the tree structure to gather postorder traversal nodes in a non-recursive (Morris traversal-like) method. Note the emphasis on edge case handling with dummy nodes and the restoration of the original tree structure using the reversal technique, ensuring the function does not permanently alter the input tree structure.