145. Binary Tree Postorder Traversal


Problem Description

Given a binary tree, the task is to perform a postorder traversal and return the values of the nodes. In postorder traversal, we visit the nodes in the following order:

  1. Traverse the left subtree in postorder.
  2. Traverse the right subtree in postorder.
  3. Visit the root node.

The challenge is to write a function that systematically visits each node in this specific order and collects the node values along the way.

Intuition

To solve this problem, you can consider three main solution approaches: recursive traversal, iterative traversal using a stack, and Morris traversal. The code provided above uses the Morris traversal method.

Recursion is the most straightforward approach where the function calls itself to traverse left and right subtrees before processing the root. It is implemented easily but uses extra space due to the function call stack.

The iterative approach with a stack emulates the recursive behavior without the need for function calls by maintaining a stack to keep track of nodes. It requires carefully managing the stack to ensure nodes are visited in the postorder sequence.

Morris traversal is a more complex but space-efficient method, as it doesn't require a stack or recursion, thus using constant space. It uses a threaded binary tree concept by creating temporary links known as threads. The intuition here is to link each node's predecessor (its rightmost child in the left subtree) back to itself, allowing traversal of the tree without additional space for a stack or recursion.

In the code provided:

  • The outer while loop is iterating over the tree nodes.
  • If a node doesn't have a right child, we capture its value and move to its left child.
  • If it has a right child, we find its predecessor and:
    • If the predecessor's left link is None, we link it back to the root (creating a temporary thread) and move to the right subtree.
    • If the predecessor's left link is already pointing to the root, we are visiting the root a second time, and hence, we break the temporary thread and move to the left subtree.

After exiting the loop, the ans list contains the values in a modified postorder sequence, and reversing it (ans[::-1]) gives the correct postorder traversal result.

This approach is more difficult to conceptualize, but it gives the elegance of an iterative solution without using additional space for a stack or the call stack, which is required in recursive solutions.

Learn more about Stack, Tree, Depth-First Search and Binary Tree patterns.

Not Sure What to Study? Take the 2-min Quiz to Find Your Missing Piece:

In a binary min heap, the maximum element can be found in:

Solution Approach

The solution uses Morris traversal, which is a space-efficient traversal method:

  1. Initialize an empty list ans to store the postorder traversal nodes' values.

  2. Start with the root node of the tree. We will use a while loop that runs as long as the root is not None.

  3. Inside the loop, if the root's right child is None, we add the root's value to the ans list, then we update the root to be its left child, as per the postorder sequence (left, right, root). Since there's no right subtree, we go left.

  4. If the root has a right child, we need to find the root's predecessor which would be the rightmost node of the left subtree.

    • We assign next to root.right and enter another while loop searching for a next.left that is not None and does not equal to root.
    • This loop is essentially moving next to the rightmost node in the left subtree of the root.
  5. After finding the predecessor, we check its left attribute:

    • If next.left is not equal to root, it means we haven't set up a temporary thread from the predecessor back to the root.
      • We record the root's value in ans.
      • Then we set next.left to root, creating a temporary thread.
      • Move root to its right subtree for the next iteration.
    • If next.left is equal to root, it means this is our second visit to the root after visiting its right subtree, and we must remove the temporary thread.
      • Set next.left back to None to restore the tree's structure.
      • Go to the next node by moving root to its left subtree.
  6. This process continues until the root becomes None, signifying that we have visited all nodes.

  7. The values stored in ans are in reverse order of the intended postorder sequence. To correct the order, we return ans[::-1], a reverse of the list, which results in the correct postorder node values.

This implementation performs the postorder traversal without using recursion or a stack, using constant extra space, which makes it highly space-efficient. The patterns and operations used—like modifying the tree structure temporarily and then restoring it—are central to the Morris traversal algorithm.

The algorithm iteratively follows the postorder sequence but constructs the answer list in reverse. This algorithm depends heavily on exploiting the tree structure in a novel way, linking and unlinking nodes as it goes.

Discover Your Strengths and Weaknesses: Take Our 2-Minute Quiz to Tailor Your Study Plan:

How many ways can you arrange the three letters A, B and C?

Example Walkthrough

Let's use a small binary tree as an example to illustrate the solution approach with Morris traversal for postorder:

Consider the following binary tree:

1    A
2   / \
3  B   C
4 / \
5D   E

Now let's walk through the Morris postorder traversal:

  1. We start at the root A. A has a right child, so we will look for the predecessor of A which is the rightmost node in the left subtree (B).

  2. We find that B has a right child E. We keep traversing to the right until we find that E's right is None and E is not already linked back to A. We link E back to A (setting E.left to A) and move to the right child of A, which is C.

  3. C has no right child, so we go straight to adding C to our list ans and traverse to its left, but since C is a leaf node, we jump back to A using the temporary thread from E.

  4. Back at A, we now cut the thread by setting E.left back to None. We add A to ans and move to its left to B.

  5. B also has a right child E, so we would go through creating a thread from B's successor D (since D is rightmost and has no right child) back to B and move to the right to E.

  6. At E, we add it to ans (as E has no right child) and go left to D.

  7. No right child for D, so we add D to ans and should move to the left, but D is a leaf node.

The sequence in ans at each step will be:

  1. Starting with an empty list ans = [].
  2. Visit C so ans = [C].
  3. Visit A so ans = [C, A].
  4. Visit E so ans = [C, A, E].
  5. Visit D so ans = [C, A, E, D].

Now we reverse ans because we collected the values in a modified postorder:

  • ans[::-1] will give us [D, E, A, C].

However, there's one missing link here, which is B. This is not seen in the order above because of Morris traversal's nature of revisiting nodes; we only add nodes under certain conditions (e.g., when a right child doesn’t exist or on a second visit to a node). A full implementation of the algorithm would successfully include B in the final list, ensuring that all nodes are traversed postorder. The correct reverse postorder ('ans' before reversing) will be [C, E, D, B, A].

So, the final postorder traversal list after reversing is [A, B, D, E, C], which aligns with the postorder sequence of left-right-root.

Not Sure What to Study? Take the 2-min Quiz:

What are the two properties the problem needs to have for dynamic programming to be applicable? (Select 2)

Python Solution

1# Definition for a binary tree node.
2class TreeNode:
3    def __init__(self, val=0, left=None, right=None):
4        self.val = val
5        self.left = left
6        self.right = right
7
8class Solution:
9    def postorderTraversal(self, root: Optional[TreeNode]) -> List[int]:
10        # Initialize an empty list to store the traversal result.
11        traversal_result = []
12
13        # Iterate while there are nodes to process.
14        while root:
15            # If there is no right child, process the current node and move to the left child.
16            if root.right is None:
17                traversal_result.append(root.val)
18                root = root.left
19            else:
20                # Find the rightmost child of the left subtree or the leftmost previous node that we have already visited.
21                predecessor = root.right
22                while predecessor.left and predecessor.left != root:
23                    predecessor = predecessor.left
24              
25                # If we have not set this relationship before, set it now and move to the right child.
26                if predecessor.left != root:
27                    traversal_result.append(root.val)
28                    predecessor.left = root
29                    root = root.right
30                else:
31                    # If we have previously visited this node (which indicates the link we created on `predecessor.left`),
32                    # Restore the tree's structure by removing the temporary link and move to the left child.
33                    predecessor.left = None
34                    root = root.left
35      
36        # Since nodes are added to traversal_result in reverse postorder (root, right, left),
37        # reverse the list to obtain the correct postorder (left, right, root) sequence.
38        return traversal_result[::-1]
39

Java Solution

1class Solution {
2    public List<Integer> postorderTraversal(TreeNode root) {
3        // Initialize an empty linked list that will store the postorder traversal elements.
4        // Using LinkedList with the addFirst method for efficient insertions at the beginning.
5        LinkedList<Integer> result = new LinkedList<>();
6
7        // Iterate while there are nodes to process
8        while (root != null) {
9            // If there is no right child, process the current node and go left
10            if (root.right == null) {
11                // Insert the current node's value at the beginning of the list
12                result.addFirst(root.val);
13                // Move to the left child
14                root = root.left;
15            } else {
16                // Find the leftmost node of the right child
17                TreeNode pre = root.right;
18                while (pre.left != null && pre.left != root) {
19                    pre = pre.left;
20                }
21                // Creating a temporary thread from right subtree's leftmost node back to root
22                if (pre.left == null) {
23                    // Add current node's value to the beginning of the list
24                    result.addFirst(root.val);
25                    // Make a temporary connection back to the root
26                    pre.left = root;
27                    // Move to the right child
28                    root = root.right;
29                } else {
30                    // If there is already a temporary thread, remove it
31                    pre.left = null;
32                    // Move to the left child of the current node
33                    root = root.left;
34                }
35            }
36        }
37        // Return the result of the postorder traversal
38        return result;
39    }
40}
41

C++ Solution

1#include <vector>
2#include <algorithm> // For reverse function
3
4// Definition for a binary tree node.
5struct TreeNode {
6    int val;
7    TreeNode *left;
8    TreeNode *right;
9    TreeNode() : val(0), left(nullptr), right(nullptr) {}
10    TreeNode(int x) : val(x), left(nullptr), right(nullptr) {}
11    TreeNode(int x, TreeNode *left, TreeNode *right) : val(x), left(left), right(right) {}
12};
13
14class Solution {
15public:
16    // Function to perform a postorder traversal of a binary tree
17    std::vector<int> postorderTraversal(TreeNode* root) {
18        std::vector<int> result; // Holds the postorder traversal result
19        // Loop until there are no nodes to process
20        while (root) {
21            // If the right subtree does not exist, process the current node and move to the left subtree
22            if (!root->right) {
23                result.push_back(root->val);
24                root = root->left;
25            } else {
26                // Find the rightmost node of the left subtree or the left child of the previous processed node
27                TreeNode* next = root->right;
28                while (next->left && next->left != root) {
29                    next = next->left;
30                }
31              
32                // Establish a temporary link so we can return to the current node after traversing its right subtree
33                if (!next->left) {
34                    result.push_back(root->val); // Process the current node
35                    next->left = root; // Establish the temporary link
36                    root = root->right; // Move to the right subtree
37                } else {
38                    next->left = nullptr; // Remove the temporary link
39                    root = root->left; // Move to the left subtree since the right subtree has been processed
40                }
41            }
42        }
43        // Reverse the results because the nodes were visited in reverse postorder
44        std::reverse(result.begin(), result.end());
45        return result;
46    }
47};
48

Typescript Solution

1// A TreeNode class definition would normally be here, 
2// but per instructions, I've omitted the class definition.
3
4function postorderTraversal(root: TreeNode | null): number[] {
5    // If the tree is empty, return an empty array
6    if (!root) return [];
7  
8    // Initialize a stack to keep track of nodes
9    let stack: TreeNode[] = [];
10    // Initialize an array to store the postorder traversal result
11    let result: number[] = [];
12    // Previous visited node
13    let previous: TreeNode | null = null;
14  
15    // Iterate while there are still nodes to process
16    while (root || stack.length > 0) {
17        // Reach the leftmost node of the current subtree
18        while (root) {
19            stack.push(root);
20            root = root.left;
21        }
22        // Peek at the node from the top of the stack
23        root = stack.pop()!;
24      
25        // If the right subtree is already visited or doesn't exist, 
26        // process the current node
27        if (!root.right || root.right === previous) {
28            result.push(root.val);
29            // Mark the current node as visited
30            previous = root;
31            // Reset root to null to indicate node processing is done
32            root = null;
33        } else {
34            // If right subtree exists, push the current node back to 
35            // the stack, and move to the right subtree
36            stack.push(root);
37            root = root.right;
38        }
39    }
40  
41    // Return the result of the postorder traversal
42    return result;
43}
44
Fast Track Your Learning with Our Quick Skills Quiz:

Depth first search can be used to find whether two components in a graph are connected.

Time and Space Complexity

The given code is attempting to perform a postorder traversal of a binary tree without using recursion. Taking a closer look:

  • The time complexity of the algorithm is O(n), where n is the number of nodes in the binary tree. This is because each edge in the tree is traversed at most twice—once when finding the inorder predecessor and once to revert the structure of the tree. The traversal ensures that each node is also processed only once.

  • The space complexity of the code is O(1), assuming that the output list does not count towards the space complexity as it is part of the required output. This is because the algorithm utilizes the tree's existing structure to traverse it by temporarily modifying the nodes' left pointers and then restoring them to their original structure, meaning no additional significant space is required other than a few pointers for manipulating the nodes.

Note: If the output list is considered in the space complexity, then the space complexity becomes O(n), since we need to store every node's value in the list.

Learn more about how to find time and space complexity quickly.


Recommended Readings


Got a question? Ask the Teaching Assistant anything you don't understand.

Still not clear? Ask in the Forum,  Discord or Submit the part you don't understand to our editors.


TA 👨‍🏫