DEV Community

Cover image for Today I Learned: Invert Binary Tree
Anzhari Purnomo
Anzhari Purnomo

Posted on

Today I Learned: Invert Binary Tree

#python #webdev #beginners #algorithms

Problem Statement

Write a function that takes in a binary tree and inverts it.

Sample Input 

tree =      1
          /   \
        2       3
      /   \   /   \
     4    5  6     7
   /   \
  8     9
Enter fullscreen mode Exit fullscreen mode

Sample Result 

tree =      1
          /   \
        3       2
      /   \   /   \
     7    6  5     4
                 /   \
                9     8
Enter fullscreen mode Exit fullscreen mode

Code #1 

def invert_binary_tree(tree):
    queue = [tree]
    while len(queue) > 0:
        cur_node = queue.pop(0)
        if cur_node is not None: 
            cur_node.left, cur_node.right = cur_node.right, cur_node.left
            queue.append(cur_node.left)
            queue.append(cur_node.right)
    return tree


# This is the class of the input binary tree.
class BinaryTree:
    def __init__(self, value):
        self.value = value
        self.left = None
        self.right = None
Enter fullscreen mode Exit fullscreen mode

Notes

  • Invert the root node of the tree first.
  • Invert = swap the left child with the right child.
  • Continue swapping the childs of the subsequent node.
  • Perform breadth-first traversal.
  • Utilize queue to perform the traversal iteratively.

Credits

Top comments (2)

Collapse
 
spachev profile image
Sasha Pachev •

Additionally, a recursive solution, tested at leetcode.com/problems/invert-binar...

class Solution {
public:
    TreeNode* invertTree(TreeNode* root) {
       if (!root)
           return NULL;
       if (root->left)
           invertTree(root->left);
       if (root->right)
           invertTree(root->right);
        TreeNode* tmp = root->right;
        root->right = root->left;
        root->left = tmp;
        return root;
    }
};
Collapse
 
anzhari profile image
Anzhari Purnomo •

Thanks for contributing the recursive approach!

Read next

confooca profile image

Unveiling the ConFoo 2025 edition!

ConFoo Developer Conference -

marcinjaniak profile image

Authorizing endpoints of external apps in k8s

Marcin Janiak -

dhyfullah_ghalebahmed_d1 profile image

Create new action in Laravel nova for download PDF for all websites pages

Dhyfullah Ghaleb ahmed -

mitchell_cheng profile image

Text compression & Code splitting & Modern image formats - Performance optimization

Mitchell -