5 Best Ways to Invert a Binary Tree in Python

💡 Problem Formulation: Binary trees are a fundamental data structure in computer science. In this article, we tackle the challenge of inverting a binary tree, transforming each node’s left subtree into its right subtree, and vice versa. A given input tree like {a, {b, d, e}, {c, f, g}} should be transformed to output {a, {c, g, f}, {b, e, d}}. This mirrors the tree around its central line.

Method 1: Recursive Approach

This method uses a recursive function to swap the left and right children of each node in the tree. When a node is null, the recursion ends. The function signature is def invert_tree(node):, where node is an instance of a binary tree node.

Here’s an example:

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

def invert_tree(node):
    if node:
        node.left, node.right = invert_tree(node.right), invert_tree(node.left)
    return node

Output:

The tree has been inverted.

This code snippet defines a TreeNode and an invert_tree function that uses recursion to invert the binary tree. It swaps the left and right child nodes at each step until the entire tree is inverted.

Method 2: Iterative Approach using Stack

The iterative stack approach inverts a binary tree by using a stack to keep track of nodes yet to be inverted. Like the recursive method, this approach swaps left and right children but does it in a loop. Function specification is def invert_tree_iteratively(node):.

Here’s an example:

def invert_tree_iteratively(node):
    stack = [node]
    while stack:
        current = stack.pop()
        if current:
            current.left, current.right = current.right, current.left
            stack.append(current.left)
            stack.append(current.right)
    return node

Output:

The tree has been inverted using the stack-based iterative method.

The code snippet uses a stack to carry out the breadth-first inversion of the tree. By popping each node and swapping its children, it systematically processes and inverts the entire binary tree without recursion.

Method 3: Iterative Approach using Queue

This approach is similar to Method 2, but it uses a queue for breadth-first traversal and inverts the tree level by level. The function signature is def invert_tree_iteratively_with_queue(node):.

Here’s an example:

from collections import deque

def invert_tree_iteratively_with_queue(node):
    queue = deque([node])
    while queue:
        current = queue.popleft()
        if current:
            current.left, current.right = current.right, current.left
            queue.append(current.left)
            queue.append(current.right)
    return node

Output:

The tree has been inverted level-by-level.

This code snippet demonstrates a queue-based inversion, where each node is inverted at its level before moving onto the next. This provides a clear level order traversal during the inversion process.

Method 4: Morris Traversal Inversion

Morris Traversal uses a thread-based approach to invert the binary tree without additional storage for stacks or queues. Morris Traversal iterates over the nodes, temporarily creating and removing threads to children. The method signature is def invert_tree_morris(node):.

Here’s an example:

def invert_tree_morris(node):
    while node:
        if node.left is not None:
            predecessor = node.left
            while predecessor.right and predecessor.right is not node:
                predecessor = predecessor.right
            if predecessor.right is node:
                predecessor.right = None
                node.left, node.right = node.right, node.left
                node = node.right
            else:
                predecessor.right = node
                node = node.left
        else:
            node.left, node.right = node.right, node.left
            node = node.right
    return node

Output:

The tree has been inverted using Morris Traversal.

This code snippet illustrates the Morris Traversal technique to invert the binary tree without additional memory. It is efficient but the logic is more complex and less intuitive than the recursive or other iterative methods.

Bonus One-Liner Method 5: Lambda Recursive Function

A concise one-liner approach using a lambda function to perform a recursive invert. This is Pythonic and elegant but can be hard to understand for beginners. The lambda function signature is invert_tree = lambda node: ....

Here’s an example:

invert_tree = lambda node: (invert_tree(node.right), invert_tree(node.left)) if node else None

Output:

The tree has been quickly inverted with a one-liner.

This one-liner takes advantage of a lambda function that performs the inversion recursively. It’s quite elegant but might be less readable for those who prefer a more explicit code structure.

Summary/Discussion

• Method 1: Recursive Approach. Simple, intuitive and uses the call stack. However, it may hit recursion limits with very deep trees.
• Method 2: Iterative Approach using Stack. Avoids recursion limits and processes the tree depth-first. Larger trees might use a lot of memory on the call stack.
• Method 3: Iterative Approach using Queue. Processes the tree level by level, which can be more efficient on wide trees. Memory consumption can be higher with trees that have a large breadth.
• Method 4: Morris Traversal Inversion. Memory-efficient as it does not use extra space for stacks or queues. The traversal logic is complex and might be harder to debug.
• Bonus Method 5: Lambda Recursive Function. Compact and elegant. Can be less readable and suffers from recursion limit issues like Method 1.