DEV Community πŸ‘©β€πŸ’»πŸ‘¨β€πŸ’»

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

Posted on

Today I Learned: Invert Binary Tree

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!

An Animated Guide to Node.js Event Lop

Node.js doesn’t stop from running other operations because of Libuv, a C++ library responsible for the event loop and asynchronously handling tasks such as network requests, DNS resolution, file system operations, data encryption, etc.

What happens under the hood when Node.js works on tasks such as database queries? We will explore it by following this piece of code step by step.