Binary Tree Postorder Traversal

Problem Statement

In the task, you are provided with the root node of a binary tree, which is a data structure where each node has at most two children named as left and right child respectively. The requirement is to perform a postorder traversal of the tree and return the values of the nodes. Postorder traversal is a type of tree traversal where the nodes are visited in the following order: left child, right child, and then the root node. This sequence is applied recursively for all nodes in the tree.

Examples

Example 1

Input:

root = [1,null,2,3]

Output:

[3,2,1]

Explanation:

Example 2

Input:

root = [1,2,3,4,5,null,8,null,null,6,7,9]

Output:

[4,6,7,5,2,9,8,3,1]

Explanation:

Example 3

Input:

root = []

Output:

[]

Example 4

Input:

root = [1]

Output:

[1]

Constraints

• The number of the nodes in the tree is in the range [0, 100].
• -100 <= Node.val <= 100

Approach and Intuition

The postorder traversal is profound in its applications, especially in mathematical expressions, and operations like delete operations on the tree. Let's break down the examples to better understand how to tackle the problem:

1. Example 1 Whit Input root = [1, null, 2, 3]:

   • In this example, the tree structure has the root node with a value of 1, no left child (null), and a right child with a value of 2 which further has one left child with a value of 3 and no right child.
   • The traversal sequence here is node 3 (left of 2), then node 2 (right of 1), and lastly node 1 (the root).
   • Thus, the output array following postorder traversal is [3, 2, 1].

2. Example 2 With Input root = [1, 2, 3, 4, 5, null, 8, null, null, 6, 7, 9]:

   • Here, the root node 1 branches out into a more complex structure with two immediate children nodes 2 and 3. Node 2 has children nodes 4 and 5, and node 3 has a null left child and a right child 8.
   • For subtree starting at node 2, postorder traversal results in [4, 6, 7, 5, 2] whereas for subtree starting at node 3, it results in [9, 8, 3].
   • Combining these traversals for full tree results in joining the outputs of subtrees in sequence followed by root, which results in [4, 6, 7, 5, 2, 9, 8, 3, 1].

3. Example 3 With Input root = []:

   • When the tree is empty (root = []), there are no nodes to visit. Hence, the postorder traversal simply returns an empty array [].

4. Example 4 With Input root = [1]:

   • For a tree that only contains the root node (no children), the postorder traversal results in [1], as there's only the root to visit.

The operations are straightforward: check for the empty tree and return an empty list, otherwise, traverse the left subtree first, followed by the right subtree, and then visit the root at last. This pattern is repeated recursively for all subtrees within the main tree. With the given constraints, this method will effectively handle all scenarios within the specified limits.

Solutions

/**
 * 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;
    }
};