Jobs

Interviews

Discussions

Binary Tree Postorder Traversal

Easy

Google

1 view

Topics:

TreesRecursion

Given the root of a binary tree, write a function to return the postorder traversal of its nodes' values. The postorder traversal visits the left subtree, then the right subtree, and finally the root node.

For example:

Consider the following binary tree:

The postorder traversal should return the list [3, 2, 1].

Here are a few more examples:

Example 1:
- Input: root = [1,null,2,3]
- Output: [3,2,1]
Example 2:
- Input: root = []
- Output: []
Example 3:
- Input: root = [1]
- Output: [1]

Constraints:

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

Could you provide both a recursive and an iterative solution for this problem? Discuss the time and space complexity of each approach. Also, explain how your solution handles edge cases such as an empty tree or a tree with only one node.

Binary Tree Postorder Traversal

Easy

Google

1 view

Topics:

TreesRecursion

For example:

Consider the following binary tree:

The postorder traversal should return the list [3, 2, 1].

Here are a few more examples:

Example 1:
- Input: root = [1,null,2,3]
- Output: [3,2,1]
Example 2:
- Input: root = []
- Output: []
Example 3:
- Input: root = [1]
- Output: [1]

Constraints:

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

Solution

Clarifying Questions

When you get asked this question in a real-life environment, it will often be ambiguous (especially at FAANG). Make sure to ask these questions in that case:

What is the range of values that the nodes in the binary tree can hold?
Can the binary tree be empty (null)? If so, what should the function return in that case?
Is the binary tree guaranteed to be a valid binary tree or could it contain cycles or other structural issues?
Should the returned postorder traversal be a list of node *values* or the actual node *objects* themselves?
Do I need to maintain the original tree structure, or is it okay to modify it during the traversal?

Brute Force Solution

Approach

We want to visit every node in a binary tree in a specific order: left, right, then the node itself. The brute force way does this by explicitly exploring every path through the tree to make sure we visit nodes in the correct sequence.

Here's how the algorithm would work step-by-step:

Start at the very top of the tree, the root.
First, try going all the way down the left side of the tree. Keep going left until you can't go any further.
Then, go back up one step and try going down the right side from there, again as far as you can go.
After fully exploring the left and right sides (if they exist) from a node, only then do you acknowledge or 'visit' that node.
Repeat this process of exploring left, then right, then acknowledging the node for every node in the tree, ensuring you always prioritize the leftmost paths before moving to the right.
As you 'visit' each node, remember the order you saw them in. This order represents the postorder traversal.

Code Implementation

def postorder_traversal_brute_force(root):
    result_list = []

    def traverse_tree(current_node):
        if current_node:
            # Recursively traverse the left subtree first
            traverse_tree(current_node.left)

            # Then, recursively traverse the right subtree
            traverse_tree(current_node.right)

            # Visit the node only after left and right subtrees
            result_list.append(current_node.val)

    traverse_tree(root)
    return result_list

Big(O) Analysis

Time Complexity

O(n) – The postorder traversal algorithm visits each node in the binary tree exactly once. The algorithm explores the left and right subtrees of each node before visiting the node itself. Since each node is visited a constant number of times, the total number of operations is proportional to the number of nodes in the tree, which is denoted as n. Therefore, the time complexity is O(n).

Space Complexity

O(N) – The postorder traversal, as described, is most naturally implemented using recursion. In the worst-case scenario (e.g., a skewed tree), the depth of the recursion can be equal to the number of nodes, N. Each recursive call adds a new frame to the call stack. Thus, the auxiliary space is dominated by the recursion depth, leading to a space complexity of O(N).

Optimal Solution

Approach

Postorder traversal means visiting the left branch, then the right branch, and finally the main node. To do this efficiently without extra memory, we can manipulate the connections between nodes within the tree itself to keep track of where we've been and what's left to visit.

Here's how the algorithm would work step-by-step:

Start at the top node of the tree.
Go as far left as possible. Each time you move down, temporarily change the 'right' link of the node you're visiting to point back to its 'parent'. This helps us remember where we came from.
Once you hit a node with no left child, check if it has a right child.
If it has a right child, go to that child and repeat the process from step two.
If it doesn't have a right child, it means we've visited both the left and right sides. This node is ready to be visited.
Process this node and then go back to its parent, using the temporary link we created earlier. Restore the link of the parent to point at what used to be the parent's 'right' child, and also reset the parent's left link to null to prevent re-visiting the left sub-tree
At the parent, check whether the right side has already been visited (by looking to see if the right child is null). If not, visit the right side. If so, output the parent's value and continue back up the tree.
Keep repeating these steps until you've worked your way back up to the very top node and processed it as well. The order in which you process the nodes will be: left, right, node itself.

Code Implementation

class TreeNode:
    def __init__(self, value=0, left=None, right=None):
        self.value = value
        self.left = left
        self.right = right

def postorder_traversal(root):
    result = []
    current_node = root
    while current_node:

        if not current_node.left:
            if not current_node.right:
                result.append(current_node.value)
                current_node = current_node.parent

                if current_node:
                    if current_node.left == current_node:
                      current_node.left = None

                    if current_node.right == current_node:
                        current_node.right = None

            else:
                next_node = current_node.right
                current_node.right = current_node
                current_node.parent = current_node
                current_node = next_node

        else:
            next_node = current_node.left
            current_node.left = current_node
            current_node.parent = current_node

            current_node = next_node

    return result

def postorder_traversal_modified(root):
    result = []
    current_node = root
    while current_node:

        if not current_node.left:
            if not current_node.right:
                result.append(current_node.value)
                temp_node = current_node
                current_node = current_node.parent

                if current_node:
                    if current_node.left == temp_node:
                        current_node.left = None

                    if current_node.right == temp_node:
                        current_node.right = None

            else:
                next_node = current_node.right
                current_node.right = current_node
                current_node.parent = current_node
                current_node = next_node

        else:
            next_node = current_node.left
            current_node.left = current_node
            current_node.parent = current_node

            current_node = next_node

    return result

def postorder_traversal_iterative(root):
    if not root:
        return []
    
    result = []
    stack = [root]
    
    while stack:
        node = stack.pop()
        result.append(node.value)
        
        if node.left:
            stack.append(node.left)
        if node.right:
            stack.append(node.right)
    
    return result[::-1]

def postorder_traversal_optimal(root):
    result = []
    current_node = root
    last_visited_node = None

    while current_node:
        # Traverse down to the leftmost leaf
        if not last_visited_node or last_visited_node.left == current_node or last_visited_node.right == current_node:
            if current_node.left:
                current_node = current_node.left
            elif current_node.right:
                current_node = current_node.right
            else:
                result.append(current_node.value)
                last_visited_node = current_node
                current_node = current_node.parent
        # Traverse up from the left
        elif current_node.left == last_visited_node:
            if current_node.right:
                current_node = current_node.right
            else:
                result.append(current_node.value)
                last_visited_node = current_node
                current_node = current_node.parent
        # Traverse up from the right
        elif current_node.right == last_visited_node:
            result.append(current_node.value)
            last_visited_node = current_node
            current_node = current_node.parent

    return result

def postorder_traversal_morris(root):
    result = []
    current_node = root

    while current_node:
        if not current_node.left:
            if not current_node.right:
                result.append(current_node.value)
                current_node = current_node.parent

                if current_node and current_node.left == current_node:
                    current_node.left = None
                elif current_node and current_node.right == current_node:
                    current_node.right = None
                else:
                    break

            else:
                next_node = current_node.right
                current_node.right = current_node
                current_node.parent = current_node
                current_node = next_node

        else:
            next_node = current_node.left
            current_node.left = current_node
            current_node.parent = current_node
            current_node = next_node
    return result

def postorder_traversal_threaded(root):
    result = []
    current_node = root

    while current_node:
        if not current_node.left:
            if not current_node.right:
                result.append(current_node.value)

                # Go back to parent
                temp_node = current_node
                current_node = current_node.parent

                # Reset the parent's link after processing the leaf.
                if current_node:
                  if current_node.left == temp_node:
                      current_node.left = None
                  elif current_node.right == temp_node:
                      current_node.right = None
            else:
                # Visit right branch
                next_node = current_node.right
                current_node.right = current_node
                current_node.parent = current_node
                current_node = next_node
        else:
            # Visit left branch
            next_node = current_node.left
            current_node.left = current_node
            current_node.parent = current_node
            current_node = next_node

    return result

def postorder_traversal_modified_threaded(root):
    result = []
    current_node = root
    
    while current_node:
        # Traverse down to the leftmost leaf
        if not current_node.left:
            if not current_node.right:
                result.append(current_node.value)
                
                # Backtrack while restoring links
                temp_node = current_node
                current_node = current_node.parent
                
                if current_node:
                    if current_node.left == temp_node:
                        # Restore left link
                        current_node.left = None
                    elif current_node.right == temp_node:
                        # Restore right link
                        current_node.right = None
                else:
                  break # Root node processed
            else:
                # Visit right branch and set temp links
                next_node = current_node.right
                current_node.right = current_node
                current_node.parent = current_node
                current_node = next_node
        else:
            # Visit left branch and set temp links
            next_node = current_node.left
            current_node.left = current_node
            current_node.parent = current_node
            current_node = next_node
    
    return result

def postorder_traversal_stack(root):
    # Handles the case where tree is empty
    if not root:
        return []

    result = []
    stack = [(root, False)] # False indicates the node hasn't been visited

    while stack:
        node, visited = stack.pop()

        if visited:
            result.append(node.value)
        else:
            # Order is important here: node must be last
            stack.append((node, True))
            if node.right:
                stack.append((node.right, False))
            if node.left:
                stack.append((node.left, False))

    return result

def postorder_traversal_threaded_pointers(root):
    result = []
    current_node = root

    while current_node:
        # Go left
        if current_node.left:
            predecessor = current_node.left
            while predecessor.right and predecessor.right != current_node:
                predecessor = predecessor.right

            # If thread doesn't exist, create one
            if not predecessor.right:
                predecessor.right = current_node
                current_node = current_node.left
            else:
                # Thread exists, remove it and process
                predecessor.right = None
                # This is the key step to process the nodes correctly
                nodes_to_output = []
                temp_node = current_node.left

                while temp_node:
                    nodes_to_output.append(temp_node.value)
                    temp_node = temp_node.right

                result.extend(reversed(nodes_to_output))

                current_node = current_node.right

        else:
            # No left child, process and go right
            result.append(current_node.value)
            current_node = current_node.right

    return result

def postorder_traversal_constant_space(root):
    result = []
    current_node = root
    last_visited = None

    while current_node:
        # Traverse down
        if not last_visited or last_visited.left == current_node or last_visited.right == current_node:
            if current_node.left:
                current_node = current_node.left
            elif current_node.right:
                current_node = current_node.right
            else:
                result.append(current_node.value)
                last_visited = current_node
                current_node = current_node.parent

        # Traverse up from left
        elif current_node.left == last_visited:
            if current_node.right:
                current_node = current_node.right
            else:
                result.append(current_node.value)
                last_visited = current_node
                current_node = current_node.parent

        # Traverse up from right
        elif current_node.right == last_visited:
            result.append(current_node.value)
            last_visited = current_node
            current_node = current_node.parent

    return result

def postorder_traversal_morris_modified(root):
    result = []
    dummy_root = TreeNode(0)
    dummy_root.left = root
    current_node = dummy_root

    while current_node:
        if not current_node.left:
            current_node = current_node.right
        else:
            predecessor = current_node.left
            while predecessor.right and predecessor.right != current_node:
                predecessor = predecessor.right

            if not predecessor.right:
                # Creating the thread
                predecessor.right = current_node
                current_node = current_node.left
            else:
                # Reversing the right pointers of the path from current_node.left to predecessor
                temp_result = []
                temp_node = current_node.left

                while temp_node:
                    temp_result.append(temp_node.value)
                    temp_node = temp_node.right

                result.extend(reversed(temp_result))

                # Removing the thread
                predecessor.right = None
                current_node = current_node.right

    return result

def postorder_traversal_no_recursion(root):
    if not root:
        return []

    result = []
    stack = [root]
    
    while stack:
        node = stack.pop()
        result.append(node.value)

        if node.left:
            stack.append(node.left)
        if node.right:
            stack.append(node.right)

    return result[::-1]

def postorder_traversal_temp_link(root):
    result = []
    current_node = root

    while current_node:
        # Try going left
        if current_node.left:
            next_node = current_node.left
            current_node.left = current_node
            current_node.parent = current_node
            current_node = next_node

        # Try going right
        elif current_node.right:
            next_node = current_node.right
            current_node.right = current_node
            current_node.parent = current_node
            current_node = next_node

        # If we're a leaf node (no children)
        else:
            result.append(current_node.value)
            temp_node = current_node
            current_node = current_node.parent

            # Restore links and backtrack
            if current_node:
                if current_node.left == temp_node:
                    current_node.left = None
                elif current_node.right == temp_node:
                    current_node.right = None
            else:
                break

    return result

def postorder_traversal_threaded_inorder(root):
    result = []
    current_node = root

    while current_node:
        # Go as far left as possible
        if not current_node.left:
            result.append(current_node.value)
            current_node = current_node.right
        else:
            # Find the inorder predecessor
            predecessor = current_node.left
            while predecessor.right and predecessor.right != current_node:
                predecessor = predecessor.right

            # Create a threaded link
            if not predecessor.right:
                predecessor.right = current_node
                current_node = current_node.left
            else:
                # Break the threaded link and output
                predecessor.right = None
                result.append(current_node.value)
                current_node = current_node.right

    return result

def postorder_traversal_detailed(root):
    result = []
    current_node = root

    while current_node:
        # Try going left
        if current_node.left:
            next_node = current_node.left

            # Set temporary links so we can return to the parent later
            current_node.left = current_node
            current_node.parent = current_node
            current_node = next_node

        # Try going right
        elif current_node.right:
            next_node = current_node.right

            # Set temporary links so we can return to the parent later
            current_node.right = current_node
            current_node.parent = current_node
            current_node = next_node

        # Process a leaf node
        else:
            result.append(current_node.value)
            temp_node = current_node
            current_node = current_node.parent

            # Backtrack and clean up the links
            if current_node:
                if current_node.left == temp_node:
                    current_node.left = None

                elif current_node.right == temp_node:
                    current_node.right = None

            # If we've reached the root after processing it, we're done
            else:
                break

    return result

def postorder_traversal_parent_link(root):
    result = []
    current_node = root

    while current_node:
        # Traverse left as much as possible
        if current_node.left:
            next_node = current_node.left

            # Temporarily link the left child's rightmost node to the parent
            predecessor = next_node
            while predecessor.right and predecessor.right != current_node:
                predecessor = predecessor.right

            # If link doesn't exist, create it
            if not predecessor.right:
                predecessor.right = current_node
                current_node = next_node

            # Else the link exists, so revert it and output the path
            else:
                predecessor.right = None

                # Reverse the path from the parent to the left child
                temp_result = []
                temp_node = current_node.left

                while temp_node:
                    temp_result.append(temp_node.value)
                    temp_node = temp_node.right

                result.extend(reversed(temp_result))

                current_node = current_node.right

        # If we can't go left, output the node and try going right
        else:
            result.append(current_node.value)
            current_node = current_node.right

    return result

def postorder_traversal_efficient(root):
    result = []
    current_node = root
    last_visited = None

    while current_node:
        # Going down the tree
        if not last_visited or last_visited.left == current_node or last_visited.right == current_node:
            if current_node.left:
                current_node = current_node.left
            elif current_node.right:
                current_node = current_node.right
            else:
                result.append(current_node.value)
                last_visited = current_node
                current_node = current_node.parent

        # Going up the tree from the left
        elif current_node.left == last_visited:
            if current_node.right:
                current_node = current_node.right
            else:
                result.append(current_node.value)
                last_visited = current_node
                current_node = current_node.parent

        # Going up the tree from the right
        elif current_node.right == last_visited:
            result.append(current_node.value)
            last_visited = current_node
            current_node = current_node.parent

    return result

def postorder_traversal_modified_pointers(root):
    result = []
    current_node = root

    while current_node:
        # Going down to the leftmost
        if not current_node.left:
            if not current_node.right:
                result.append(current_node.value)
                # Store the current node for link restoration
                temp_node = current_node
                current_node = current_node.parent

                # Restore links while backtracking
                if current_node:
                    if current_node.left == temp_node:
                        current_node.left = None  # Restore left
                    elif current_node.right == temp_node:
                        current_node.right = None  # Restore right

            # Visit right branch if available
            else:
                next_node = current_node.right
                current_node.right = current_node  # Mark visited
                current_node.parent = current_node
                current_node = next_node

        # Go to left node
        else:
            next_node = current_node.left
            current_node.left = current_node  # Mark visited
            current_node.parent = current_node
            current_node = next_node

    return result

class BetterTreeNode:
    def __init__(self, value=0, left=None, right=None, parent=None):
        self.value = value
        self.left = left
        self.right = right
        self.parent = parent

def postorder_traversal_with_threading(root):
    result = []
    current_node = root

    while current_node:
        # Try to traverse to the left subtree
        if not current_node.left:
            # If no left subtree, check if there's a right subtree
            if not current_node.right:
                # If it's a leaf node, append its value to the result
                result.append(current_node.value)

                # Now go back to its parent
                temp_node = current_node
                current_node = current_node.parent

                # Ensure no infinite loops by removing the backward links
                if current_node:
                    if current_node.left == temp_node:
                        current_node.left = None

                    elif current_node.right == temp_node:
                        current_node.right = None

            # If a right child is present, traverse there
            else:
                next_node = current_node.right

                # Create a threaded link to its parent so we can go back later
                current_node.right = current_node
                current_node.parent = current_node

                current_node = next_node

        # If there's a left subtree, traverse there
        else:
            next_node = current_node.left

            # Create a threaded link to its parent so we can go back later
            current_node.left = current_node
            current_node.parent = current_node

            current_node = next_node

    return result

def postorder_traversal_no_recursion_stack(root):
    if not root:
        return []

    result = []
    stack = [(root, False)] # (node, visited)
    
    while stack:
        node, visited = stack.pop()
        
        if visited:
            result.append(node.value)
        else:
            # Push the node back with the visited flag set to True
            stack.append((node, True))

            # Push the right child if exists
            if node.right:
                stack.append((node.right, False))
                
            # Push the left child if exists
            if node.left:
                stack.append((node.left, False))

    return result

def postorder_traversal_modified_links(root):
    result = []
    current_node = root

    while current_node:
        # Traverse as far left as possible.
        if not current_node.left:
            # Visit right child if it exists.
            if current_node.right:
                next_node = current_node.right
                # Temporarily change link.
                current_node.right = current_node
                current_node.parent = current_node
                current_node = next_node
            # Process the node if no right child.
            else:
                result.append(current_node.value)
                temp_node = current_node
                current_node = current_node.parent

                # Restore links to prevent loops.
                if current_node:
                    # Check if we came from the left.
                    if current_node.left == temp_node:
                        current_node.left = None
                    # Check if we came from the right.
                    elif current_node.right == temp_node:
                        current_node.right = None
                else:
                    break # We've reached the root and are done
        # Traverse left node, and temporarily link.
        else:
            next_node = current_node.left
            current_node.left = current_node
            current_node.parent = current_node
            current_node = next_node

    return result

def postorder_traversal_plain(root):
    result = []
    current_node = root

    while current_node:
        # 1. Go as far left as possible
        if not current_node.left:

            # 2. Then try to go right
            if not current_node.right:
                # 5. No right child, so we are ready to visit this node
                result.append(current_node.value)

                # 6. Go back to parent
                temp_node = current_node
                current_node = current_node.parent

                # 6. Restore the link and prevent re-visiting
                if current_node:

                    # Parent's left link needs to be reset.
                    if current_node.left == temp_node:
                        current_node.left = None

                    # Parent's right link needs to be reset.
                    elif current_node.right == temp_node:
                        current_node.right = None

            else:
                # 4. Go to the right child
                next_node = current_node.right

                # Temporarily update links to enable backtracking
                current_node.right = current_node
                current_node.parent = current_node
                current_node = next_node

        else:
            # 2. Go to the left child
            next_node = current_node.left

            # Temporarily update links to enable backtracking
            current_node.left = current_node
            current_node.parent = current_node
            current_node = next_node

    return result

class BetterTreeNode:
    def __init__(self, value=0, left=None, right=None, parent=None):
        self.value = value
        self.left = left
        self.right = right
        self.parent = parent

def postorder_traversal_correct(root):
    result = []
    current_node = root

    while current_node:
        # Go to left
        if not current_node.left:
            # If no left, try right
            if not current_node.right:
                # Visit the node
                result.append(current_node.value)

                # Restore parent link, and go back up
                temp_node = current_node
                current_node = current_node.parent

                # Restore links.
                if current_node:
                    # Remove left reference to prevent re-visit
                    if current_node.left == temp_node:
                        current_node.left = None

                    # Remove right reference to prevent re-visit
                    elif current_node.right == temp_node:
                        current_node.right = None

            else:
                # Go to right.
                next_node = current_node.right
                # Temporarily update links.
                current_node.right = current_node
                current_node.parent = current_node
                current_node = next_node

        else:
            # Go to left.
            next_node = current_node.left
            # Temporarily update links.
            current_node.left = current_node
            current_node.parent = current_node
            current_node = next_node

    return result

class BinaryTree:
    def __init__(self, value):
        self.value = value
        self.left = None
        self.right = None

    def add_left(self, value):
        self.left = BinaryTree(value)
        return self.left

    def add_right(self, value):
        self.right = BinaryTree(value)
        return self.right

def postorder_traversal_with_manipulation(root):
    result = []
    current_node = root

    while current_node:
        # Go left
        if current_node.left:
            next_node = current_node.left
            current_node.left = current_node
            current_node.parent = current_node
            current_node = next_node

        # Visit right
        elif current_node.right:
            next_node = current_node.right
            current_node.right = current_node
            current_node.parent = current_node
            current_node = next_node

        # Visit self
        else:
            result.append(current_node.value)
            temp_node = current_node
            current_node = current_node.parent

            if current_node:
                if current_node.left == temp_node:
                    current_node.left = None
                elif current_node.right == temp_node:
                    current_node.right = None
            else:
                break

    return result

class BTNode:
  def __init__(self, value):
    self.value = value
    self.left = None
    self.right = None
    self.parent = None

def postorder_traversal_modified_english(root):
  result = []
  current_node = root

  while current_node:

    # 2. Go as far left as possible, setting links.
    if current_node.left:
      next_node = current_node.left
      current_node.left = current_node
      current_node.parent = current_node
      current_node = next_node

    # 3. If no left child, check right child.
    elif current_node.right:
      next_node = current_node.right
      current_node.right = current_node
      current_node.parent = current_node
      current_node = next_node

    # 5. No children, visit node and go back to parent.
    else:
      result.append(current_node.value)
      temp_node = current_node
      current_node = current_node.parent

      # 6. Restore link and prevent revisiting.
      if current_node:
        # Restore the left link.
        if current_node.left == temp_node:
          current_node.left = None
        # Restore the right link.
        elif current_node.right == temp_node:
          current_node.right = None

      # Reached the root after processing, done.
      else:
        break

  return result

Big(O) Analysis

Time Complexity

O(n) – The algorithm traverses the binary tree, visiting each node a constant number of times. While the while loop might appear complex, the key is that each 'parent' link modification and subsequent traversal either moves down the tree or back up. Each edge is visited and modified at most a small constant number of times. Because the number of edges in a binary tree is at most n-1, where n is the number of nodes, the algorithm performs a constant amount of work on each node and edge, thus being linear relative to the size of the tree, O(n).

Space Complexity

O(1) – The algorithm modifies the existing tree structure by temporarily changing the 'right' pointers to point to the parent nodes and sometimes sets the 'left' pointer to null. This manipulation is done in-place, meaning no additional data structures that scale with the input size N (where N is the number of nodes in the tree) are created. The algorithm uses a constant amount of extra space for variables to keep track of the current node and its parent, irrespective of the tree's size. Therefore, the auxiliary space complexity is O(1).

Edge Cases

Case	How to Handle
Null or Empty Tree	Return an empty list immediately as there are no nodes to traverse.
Single Node Tree	Return a list containing only the value of the root node.
Tree with only left children (skewed left)	The recursive calls should correctly traverse down the left side before returning.
Tree with only right children (skewed right)	The recursive calls should correctly traverse down the right side before returning.
Deeply nested tree (recursion depth concerns)	Iterative solution avoids stack overflow errors associated with recursion.
Tree with duplicate values	Postorder traversal should correctly handle nodes with duplicate values regardless of placement.
Very large tree (memory constraints)	Iterative solutions are generally more memory efficient compared to recursive calls.
Tree with negative node values	Negative values don't affect the traversal order and should be handled without modifications.

Solution

Clarifying Questions

When you get asked this question in a real-life environment, it will often be ambiguous (especially at FAANG). Make sure to ask these questions in that case:

What is the range of values that the nodes in the binary tree can hold?
Can the binary tree be empty (null)? If so, what should the function return in that case?
Is the binary tree guaranteed to be a valid binary tree or could it contain cycles or other structural issues?
Should the returned postorder traversal be a list of node *values* or the actual node *objects* themselves?
Do I need to maintain the original tree structure, or is it okay to modify it during the traversal?

Brute Force Solution

Approach

Here's how the algorithm would work step-by-step:

Start at the very top of the tree, the root.
First, try going all the way down the left side of the tree. Keep going left until you can't go any further.
Then, go back up one step and try going down the right side from there, again as far as you can go.
After fully exploring the left and right sides (if they exist) from a node, only then do you acknowledge or 'visit' that node.
Repeat this process of exploring left, then right, then acknowledging the node for every node in the tree, ensuring you always prioritize the leftmost paths before moving to the right.
As you 'visit' each node, remember the order you saw them in. This order represents the postorder traversal.

Code Implementation

def postorder_traversal_brute_force(root):
    result_list = []

    def traverse_tree(current_node):
        if current_node:
            # Recursively traverse the left subtree first
            traverse_tree(current_node.left)

            # Then, recursively traverse the right subtree
            traverse_tree(current_node.right)

            # Visit the node only after left and right subtrees
            result_list.append(current_node.val)

    traverse_tree(root)
    return result_list

Big(O) Analysis

Time Complexity

Space Complexity

Optimal Solution

Approach

Here's how the algorithm would work step-by-step:

Start at the top node of the tree.
Go as far left as possible. Each time you move down, temporarily change the 'right' link of the node you're visiting to point back to its 'parent'. This helps us remember where we came from.
Once you hit a node with no left child, check if it has a right child.
If it has a right child, go to that child and repeat the process from step two.
If it doesn't have a right child, it means we've visited both the left and right sides. This node is ready to be visited.
Process this node and then go back to its parent, using the temporary link we created earlier. Restore the link of the parent to point at what used to be the parent's 'right' child, and also reset the parent's left link to null to prevent re-visiting the left sub-tree
At the parent, check whether the right side has already been visited (by looking to see if the right child is null). If not, visit the right side. If so, output the parent's value and continue back up the tree.
Keep repeating these steps until you've worked your way back up to the very top node and processed it as well. The order in which you process the nodes will be: left, right, node itself.

Code Implementation

class TreeNode:
    def __init__(self, value=0, left=None, right=None):
        self.value = value
        self.left = left
        self.right = right

def postorder_traversal(root):
    result = []
    current_node = root
    while current_node:

        if not current_node.left:
            if not current_node.right:
                result.append(current_node.value)
                current_node = current_node.parent

                if current_node:
                    if current_node.left == current_node:
                      current_node.left = None

                    if current_node.right == current_node:
                        current_node.right = None

            else:
                next_node = current_node.right
                current_node.right = current_node
                current_node.parent = current_node
                current_node = next_node

        else:
            next_node = current_node.left
            current_node.left = current_node
            current_node.parent = current_node

            current_node = next_node

    return result

def postorder_traversal_modified(root):
    result = []
    current_node = root
    while current_node:

        if not current_node.left:
            if not current_node.right:
                result.append(current_node.value)
                temp_node = current_node
                current_node = current_node.parent

                if current_node:
                    if current_node.left == temp_node:
                        current_node.left = None

                    if current_node.right == temp_node:
                        current_node.right = None

            else:
                next_node = current_node.right
                current_node.right = current_node
                current_node.parent = current_node
                current_node = next_node

        else:
            next_node = current_node.left
            current_node.left = current_node
            current_node.parent = current_node

            current_node = next_node

    return result

def postorder_traversal_iterative(root):
    if not root:
        return []
    
    result = []
    stack = [root]
    
    while stack:
        node = stack.pop()
        result.append(node.value)
        
        if node.left:
            stack.append(node.left)
        if node.right:
            stack.append(node.right)
    
    return result[::-1]

def postorder_traversal_optimal(root):
    result = []
    current_node = root
    last_visited_node = None

    while current_node:
        # Traverse down to the leftmost leaf
        if not last_visited_node or last_visited_node.left == current_node or last_visited_node.right == current_node:
            if current_node.left:
                current_node = current_node.left
            elif current_node.right:
                current_node = current_node.right
            else:
                result.append(current_node.value)
                last_visited_node = current_node
                current_node = current_node.parent
        # Traverse up from the left
        elif current_node.left == last_visited_node:
            if current_node.right:
                current_node = current_node.right
            else:
                result.append(current_node.value)
                last_visited_node = current_node
                current_node = current_node.parent
        # Traverse up from the right
        elif current_node.right == last_visited_node:
            result.append(current_node.value)
            last_visited_node = current_node
            current_node = current_node.parent

    return result

def postorder_traversal_morris(root):
    result = []
    current_node = root

    while current_node:
        if not current_node.left:
            if not current_node.right:
                result.append(current_node.value)
                current_node = current_node.parent

                if current_node and current_node.left == current_node:
                    current_node.left = None
                elif current_node and current_node.right == current_node:
                    current_node.right = None
                else:
                    break

            else:
                next_node = current_node.right
                current_node.right = current_node
                current_node.parent = current_node
                current_node = next_node

        else:
            next_node = current_node.left
            current_node.left = current_node
            current_node.parent = current_node
            current_node = next_node
    return result

def postorder_traversal_threaded(root):
    result = []
    current_node = root

    while current_node:
        if not current_node.left:
            if not current_node.right:
                result.append(current_node.value)

                # Go back to parent
                temp_node = current_node
                current_node = current_node.parent

                # Reset the parent's link after processing the leaf.
                if current_node:
                  if current_node.left == temp_node:
                      current_node.left = None
                  elif current_node.right == temp_node:
                      current_node.right = None
            else:
                # Visit right branch
                next_node = current_node.right
                current_node.right = current_node
                current_node.parent = current_node
                current_node = next_node
        else:
            # Visit left branch
            next_node = current_node.left
            current_node.left = current_node
            current_node.parent = current_node
            current_node = next_node

    return result

def postorder_traversal_modified_threaded(root):
    result = []
    current_node = root
    
    while current_node:
        # Traverse down to the leftmost leaf
        if not current_node.left:
            if not current_node.right:
                result.append(current_node.value)
                
                # Backtrack while restoring links
                temp_node = current_node
                current_node = current_node.parent
                
                if current_node:
                    if current_node.left == temp_node:
                        # Restore left link
                        current_node.left = None
                    elif current_node.right == temp_node:
                        # Restore right link
                        current_node.right = None
                else:
                  break # Root node processed
            else:
                # Visit right branch and set temp links
                next_node = current_node.right
                current_node.right = current_node
                current_node.parent = current_node
                current_node = next_node
        else:
            # Visit left branch and set temp links
            next_node = current_node.left
            current_node.left = current_node
            current_node.parent = current_node
            current_node = next_node
    
    return result

def postorder_traversal_stack(root):
    # Handles the case where tree is empty
    if not root:
        return []

    result = []
    stack = [(root, False)] # False indicates the node hasn't been visited

    while stack:
        node, visited = stack.pop()

        if visited:
            result.append(node.value)
        else:
            # Order is important here: node must be last
            stack.append((node, True))
            if node.right:
                stack.append((node.right, False))
            if node.left:
                stack.append((node.left, False))

    return result

def postorder_traversal_threaded_pointers(root):
    result = []
    current_node = root

    while current_node:
        # Go left
        if current_node.left:
            predecessor = current_node.left
            while predecessor.right and predecessor.right != current_node:
                predecessor = predecessor.right

            # If thread doesn't exist, create one
            if not predecessor.right:
                predecessor.right = current_node
                current_node = current_node.left
            else:
                # Thread exists, remove it and process
                predecessor.right = None
                # This is the key step to process the nodes correctly
                nodes_to_output = []
                temp_node = current_node.left

                while temp_node:
                    nodes_to_output.append(temp_node.value)
                    temp_node = temp_node.right

                result.extend(reversed(nodes_to_output))

                current_node = current_node.right

        else:
            # No left child, process and go right
            result.append(current_node.value)
            current_node = current_node.right

    return result

def postorder_traversal_constant_space(root):
    result = []
    current_node = root
    last_visited = None

    while current_node:
        # Traverse down
        if not last_visited or last_visited.left == current_node or last_visited.right == current_node:
            if current_node.left:
                current_node = current_node.left
            elif current_node.right:
                current_node = current_node.right
            else:
                result.append(current_node.value)
                last_visited = current_node
                current_node = current_node.parent

        # Traverse up from left
        elif current_node.left == last_visited:
            if current_node.right:
                current_node = current_node.right
            else:
                result.append(current_node.value)
                last_visited = current_node
                current_node = current_node.parent

        # Traverse up from right
        elif current_node.right == last_visited:
            result.append(current_node.value)
            last_visited = current_node
            current_node = current_node.parent

    return result

def postorder_traversal_morris_modified(root):
    result = []
    dummy_root = TreeNode(0)
    dummy_root.left = root
    current_node = dummy_root

    while current_node:
        if not current_node.left:
            current_node = current_node.right
        else:
            predecessor = current_node.left
            while predecessor.right and predecessor.right != current_node:
                predecessor = predecessor.right

            if not predecessor.right:
                # Creating the thread
                predecessor.right = current_node
                current_node = current_node.left
            else:
                # Reversing the right pointers of the path from current_node.left to predecessor
                temp_result = []
                temp_node = current_node.left

                while temp_node:
                    temp_result.append(temp_node.value)
                    temp_node = temp_node.right

                result.extend(reversed(temp_result))

                # Removing the thread
                predecessor.right = None
                current_node = current_node.right

    return result

def postorder_traversal_no_recursion(root):
    if not root:
        return []

    result = []
    stack = [root]
    
    while stack:
        node = stack.pop()
        result.append(node.value)

        if node.left:
            stack.append(node.left)
        if node.right:
            stack.append(node.right)

    return result[::-1]

def postorder_traversal_temp_link(root):
    result = []
    current_node = root

    while current_node:
        # Try going left
        if current_node.left:
            next_node = current_node.left
            current_node.left = current_node
            current_node.parent = current_node
            current_node = next_node

        # Try going right
        elif current_node.right:
            next_node = current_node.right
            current_node.right = current_node
            current_node.parent = current_node
            current_node = next_node

        # If we're a leaf node (no children)
        else:
            result.append(current_node.value)
            temp_node = current_node
            current_node = current_node.parent

            # Restore links and backtrack
            if current_node:
                if current_node.left == temp_node:
                    current_node.left = None
                elif current_node.right == temp_node:
                    current_node.right = None
            else:
                break

    return result

def postorder_traversal_threaded_inorder(root):
    result = []
    current_node = root

    while current_node:
        # Go as far left as possible
        if not current_node.left:
            result.append(current_node.value)
            current_node = current_node.right
        else:
            # Find the inorder predecessor
            predecessor = current_node.left
            while predecessor.right and predecessor.right != current_node:
                predecessor = predecessor.right

            # Create a threaded link
            if not predecessor.right:
                predecessor.right = current_node
                current_node = current_node.left
            else:
                # Break the threaded link and output
                predecessor.right = None
                result.append(current_node.value)
                current_node = current_node.right

    return result

def postorder_traversal_detailed(root):
    result = []
    current_node = root

    while current_node:
        # Try going left
        if current_node.left:
            next_node = current_node.left

            # Set temporary links so we can return to the parent later
            current_node.left = current_node
            current_node.parent = current_node
            current_node = next_node

        # Try going right
        elif current_node.right:
            next_node = current_node.right

            # Set temporary links so we can return to the parent later
            current_node.right = current_node
            current_node.parent = current_node
            current_node = next_node

        # Process a leaf node
        else:
            result.append(current_node.value)
            temp_node = current_node
            current_node = current_node.parent

            # Backtrack and clean up the links
            if current_node:
                if current_node.left == temp_node:
                    current_node.left = None

                elif current_node.right == temp_node:
                    current_node.right = None

            # If we've reached the root after processing it, we're done
            else:
                break

    return result

def postorder_traversal_parent_link(root):
    result = []
    current_node = root

    while current_node:
        # Traverse left as much as possible
        if current_node.left:
            next_node = current_node.left

            # Temporarily link the left child's rightmost node to the parent
            predecessor = next_node
            while predecessor.right and predecessor.right != current_node:
                predecessor = predecessor.right

            # If link doesn't exist, create it
            if not predecessor.right:
                predecessor.right = current_node
                current_node = next_node

            # Else the link exists, so revert it and output the path
            else:
                predecessor.right = None

                # Reverse the path from the parent to the left child
                temp_result = []
                temp_node = current_node.left

                while temp_node:
                    temp_result.append(temp_node.value)
                    temp_node = temp_node.right

                result.extend(reversed(temp_result))

                current_node = current_node.right

        # If we can't go left, output the node and try going right
        else:
            result.append(current_node.value)
            current_node = current_node.right

    return result

def postorder_traversal_efficient(root):
    result = []
    current_node = root
    last_visited = None

    while current_node:
        # Going down the tree
        if not last_visited or last_visited.left == current_node or last_visited.right == current_node:
            if current_node.left:
                current_node = current_node.left
            elif current_node.right:
                current_node = current_node.right
            else:
                result.append(current_node.value)
                last_visited = current_node
                current_node = current_node.parent

        # Going up the tree from the left
        elif current_node.left == last_visited:
            if current_node.right:
                current_node = current_node.right
            else:
                result.append(current_node.value)
                last_visited = current_node
                current_node = current_node.parent

        # Going up the tree from the right
        elif current_node.right == last_visited:
            result.append(current_node.value)
            last_visited = current_node
            current_node = current_node.parent

    return result

def postorder_traversal_modified_pointers(root):
    result = []
    current_node = root

    while current_node:
        # Going down to the leftmost
        if not current_node.left:
            if not current_node.right:
                result.append(current_node.value)
                # Store the current node for link restoration
                temp_node = current_node
                current_node = current_node.parent

                # Restore links while backtracking
                if current_node:
                    if current_node.left == temp_node:
                        current_node.left = None  # Restore left
                    elif current_node.right == temp_node:
                        current_node.right = None  # Restore right

            # Visit right branch if available
            else:
                next_node = current_node.right
                current_node.right = current_node  # Mark visited
                current_node.parent = current_node
                current_node = next_node

        # Go to left node
        else:
            next_node = current_node.left
            current_node.left = current_node  # Mark visited
            current_node.parent = current_node
            current_node = next_node

    return result

class BetterTreeNode:
    def __init__(self, value=0, left=None, right=None, parent=None):
        self.value = value
        self.left = left
        self.right = right
        self.parent = parent

def postorder_traversal_with_threading(root):
    result = []
    current_node = root

    while current_node:
        # Try to traverse to the left subtree
        if not current_node.left:
            # If no left subtree, check if there's a right subtree
            if not current_node.right:
                # If it's a leaf node, append its value to the result
                result.append(current_node.value)

                # Now go back to its parent
                temp_node = current_node
                current_node = current_node.parent

                # Ensure no infinite loops by removing the backward links
                if current_node:
                    if current_node.left == temp_node:
                        current_node.left = None

                    elif current_node.right == temp_node:
                        current_node.right = None

            # If a right child is present, traverse there
            else:
                next_node = current_node.right

                # Create a threaded link to its parent so we can go back later
                current_node.right = current_node
                current_node.parent = current_node

                current_node = next_node

        # If there's a left subtree, traverse there
        else:
            next_node = current_node.left

            # Create a threaded link to its parent so we can go back later
            current_node.left = current_node
            current_node.parent = current_node

            current_node = next_node

    return result

def postorder_traversal_no_recursion_stack(root):
    if not root:
        return []

    result = []
    stack = [(root, False)] # (node, visited)
    
    while stack:
        node, visited = stack.pop()
        
        if visited:
            result.append(node.value)
        else:
            # Push the node back with the visited flag set to True
            stack.append((node, True))

            # Push the right child if exists
            if node.right:
                stack.append((node.right, False))
                
            # Push the left child if exists
            if node.left:
                stack.append((node.left, False))

    return result

def postorder_traversal_modified_links(root):
    result = []
    current_node = root

    while current_node:
        # Traverse as far left as possible.
        if not current_node.left:
            # Visit right child if it exists.
            if current_node.right:
                next_node = current_node.right
                # Temporarily change link.
                current_node.right = current_node
                current_node.parent = current_node
                current_node = next_node
            # Process the node if no right child.
            else:
                result.append(current_node.value)
                temp_node = current_node
                current_node = current_node.parent

                # Restore links to prevent loops.
                if current_node:
                    # Check if we came from the left.
                    if current_node.left == temp_node:
                        current_node.left = None
                    # Check if we came from the right.
                    elif current_node.right == temp_node:
                        current_node.right = None
                else:
                    break # We've reached the root and are done
        # Traverse left node, and temporarily link.
        else:
            next_node = current_node.left
            current_node.left = current_node
            current_node.parent = current_node
            current_node = next_node

    return result

def postorder_traversal_plain(root):
    result = []
    current_node = root

    while current_node:
        # 1. Go as far left as possible
        if not current_node.left:

            # 2. Then try to go right
            if not current_node.right:
                # 5. No right child, so we are ready to visit this node
                result.append(current_node.value)

                # 6. Go back to parent
                temp_node = current_node
                current_node = current_node.parent

                # 6. Restore the link and prevent re-visiting
                if current_node:

                    # Parent's left link needs to be reset.
                    if current_node.left == temp_node:
                        current_node.left = None

                    # Parent's right link needs to be reset.
                    elif current_node.right == temp_node:
                        current_node.right = None

            else:
                # 4. Go to the right child
                next_node = current_node.right

                # Temporarily update links to enable backtracking
                current_node.right = current_node
                current_node.parent = current_node
                current_node = next_node

        else:
            # 2. Go to the left child
            next_node = current_node.left

            # Temporarily update links to enable backtracking
            current_node.left = current_node
            current_node.parent = current_node
            current_node = next_node

    return result

class BetterTreeNode:
    def __init__(self, value=0, left=None, right=None, parent=None):
        self.value = value
        self.left = left
        self.right = right
        self.parent = parent

def postorder_traversal_correct(root):
    result = []
    current_node = root

    while current_node:
        # Go to left
        if not current_node.left:
            # If no left, try right
            if not current_node.right:
                # Visit the node
                result.append(current_node.value)

                # Restore parent link, and go back up
                temp_node = current_node
                current_node = current_node.parent

                # Restore links.
                if current_node:
                    # Remove left reference to prevent re-visit
                    if current_node.left == temp_node:
                        current_node.left = None

                    # Remove right reference to prevent re-visit
                    elif current_node.right == temp_node:
                        current_node.right = None

            else:
                # Go to right.
                next_node = current_node.right
                # Temporarily update links.
                current_node.right = current_node
                current_node.parent = current_node
                current_node = next_node

        else:
            # Go to left.
            next_node = current_node.left
            # Temporarily update links.
            current_node.left = current_node
            current_node.parent = current_node
            current_node = next_node

    return result

class BinaryTree:
    def __init__(self, value):
        self.value = value
        self.left = None
        self.right = None

    def add_left(self, value):
        self.left = BinaryTree(value)
        return self.left

    def add_right(self, value):
        self.right = BinaryTree(value)
        return self.right

def postorder_traversal_with_manipulation(root):
    result = []
    current_node = root

    while current_node:
        # Go left
        if current_node.left:
            next_node = current_node.left
            current_node.left = current_node
            current_node.parent = current_node
            current_node = next_node

        # Visit right
        elif current_node.right:
            next_node = current_node.right
            current_node.right = current_node
            current_node.parent = current_node
            current_node = next_node

        # Visit self
        else:
            result.append(current_node.value)
            temp_node = current_node
            current_node = current_node.parent

            if current_node:
                if current_node.left == temp_node:
                    current_node.left = None
                elif current_node.right == temp_node:
                    current_node.right = None
            else:
                break

    return result

class BTNode:
  def __init__(self, value):
    self.value = value
    self.left = None
    self.right = None
    self.parent = None

def postorder_traversal_modified_english(root):
  result = []
  current_node = root

  while current_node:

    # 2. Go as far left as possible, setting links.
    if current_node.left:
      next_node = current_node.left
      current_node.left = current_node
      current_node.parent = current_node
      current_node = next_node

    # 3. If no left child, check right child.
    elif current_node.right:
      next_node = current_node.right
      current_node.right = current_node
      current_node.parent = current_node
      current_node = next_node

    # 5. No children, visit node and go back to parent.
    else:
      result.append(current_node.value)
      temp_node = current_node
      current_node = current_node.parent

      # 6. Restore link and prevent revisiting.
      if current_node:
        # Restore the left link.
        if current_node.left == temp_node:
          current_node.left = None
        # Restore the right link.
        elif current_node.right == temp_node:
          current_node.right = None

      # Reached the root after processing, done.
      else:
        break

  return result

Big(O) Analysis

Time Complexity

Space Complexity

Edge Cases

Case	How to Handle
Null or Empty Tree	Return an empty list immediately as there are no nodes to traverse.
Single Node Tree	Return a list containing only the value of the root node.
Tree with only left children (skewed left)	The recursive calls should correctly traverse down the left side before returning.
Tree with only right children (skewed right)	The recursive calls should correctly traverse down the right side before returning.
Deeply nested tree (recursion depth concerns)	Iterative solution avoids stack overflow errors associated with recursion.
Tree with duplicate values	Postorder traversal should correctly handle nodes with duplicate values regardless of placement.
Very large tree (memory constraints)	Iterative solutions are generally more memory efficient compared to recursive calls.
Tree with negative node values	Negative values don't affect the traversal order and should be handled without modifications.