Code360 powered by Coding Ninjas X Naukri.com. Code360 powered by Coding Ninjas X Naukri.com
Table of contents
1.
Introduction 
1.1.
Problem Statement
1.2.
Sample Examples 
2.
Recursive Approach 
2.1.
Steps of Algorithm
2.2.
Implementation in C++
2.2.1.
Complexity Analysis
3.
Iterative Approach 
3.1.
Implementation in C++
3.1.1.
Complexity Analysis
4.
Frequently Asked Questions
4.1.
What are tree traversals?  
4.2.
What is the difference between Breadth-first Search and Depth-first search? 
4.3.
What is the difference between a binary tree and a binary search tree?
4.4.
What is the binary heap? 
5.
Conclusion 
Last Updated: Mar 27, 2024
Medium

Flip Binary Tree

Master Power BI using Netflix Data
Speaker
Ashwin Goyal
Product @
18 Jun, 2024 @ 01:30 PM

Introduction 

This article will discuss the problem of flip binary trees in the right direction, which is clockwise. There is a prerequisite to solving this problem. You need to understand traversal in the binary tree. You can refer to this blog on coding ninjas to learn more about this. 

Problem Statement

The problem states that we are given a binary tree, and we need to flip the binary tree in the right direction, i.e., The leftmost node becomes the flipped tree's root, its parent becomes its right child, and its right sibling becomes its left child in the flip process, and this should be repeated for all leftmost nodes recursively.

See the sample example for a better understanding of the question

Sample Examples 

Input 1: 

Output 1: 

 

Input 2: 

Outpu 2: 

Recursive Approach 

The idea is simple, main rotation code, is given as 

root->left->left = root->right;
root->left->right = root;
root->left = NULL;
root->right = NULL;

 

To better understand this code, we will dry run on a binary tree.

Steps of Algorithm

  • Take the input of the binary tree.
  • Call the function FlipBinaryTree(), and pass the root of the binary tree. 
  • Apply the above algorithm, and finally print the level order traversal of the binary tree. 
  • We have finally obtained the flipped tree. 

Implementation in C++

// C++ code to flip binary tree
#include <bits/stdc++.h>
using namespace std;
// binary tree class
class BinaryTreeNode
{
public:
    int val;
    BinaryTreeNode *left, *right;
    // constructor
    BinaryTreeNode(int val)
    {
        this->val = val;
        this->left = NULL;
        this->right = NULL;
    }
};
BinaryTreeNode *FlipBinaryTree(BinaryTreeNode *root)
{
    // if we reach the NULL node, or the tree Node, simply return the root
    if (!root || (!root->left) && (!root->right))
        return root;
    BinaryTreeNode *flippedTree = FlipBinaryTree(root->left);
    root->left->left = root->right;
    root->left->right = root;
    root->left = NULL;
    root->right = NULL;
    return flippedTree;
}
void LevelOrderTraversal(BinaryTreeNode *root)
{
    // initiliazing the queue to do the level order traversal
    queue<BinaryTreeNode *> q;
    // pushing the root into the queue
    q.push(root);
    while (!q.empty())
    {
        int len = q.size();
        while (len--)
        {
            BinaryTreeNode *node = q.front();
            q.pop();
            if (node->left)
            {
                q.push(node->left);
            }
            if (node->right)
            {
                q.push(node->right);
            }
            cout << node->val << " ";
        }
        cout << endl;
    }
}
int main()
{
    // building the binary tree
    BinaryTreeNode *root = new BinaryTreeNode(50);
    
    root->left = new BinaryTreeNode(20);
    root->right = new BinaryTreeNode(40);

    // printing the binary tree before calling the flip binary tree function
    cout << "Printing before calling the FlipBinaryTree function" << endl;
    
    LevelOrderTraversal(root);
    
    root = FlipBinaryTree(root);
    
    // printing the binary tree after calling the flip binary tree function
    cout << "Printing after calling the FlipBinaryTree function" << endl;
    LevelOrderTraversal(root);
    cout << endl;
}

 

Output:

Printing before calling the FlipBinaryTree function
50
20 40
Printing after calling the FlipBinaryTree function
20
40 50

 

Complexity Analysis

Time Complexity: O(N)

We are only doing linear traversal of the tree, so only linear time complexity. 

Space Complexity: O(1)

We are not taking any extra space to flip the binary tree. 

Get the tech career you deserve, faster!
Connect with our expert counsellors to understand how to hack your way to success
User rating 4.7/5
1:1 doubt support
95% placement record
Akash Pal
Senior Software Engineer
326% Hike After Job Bootcamp
Himanshu Gusain
Programmer Analyst
32 LPA After Job Bootcamp
After Job
Bootcamp

Iterative Approach 

The logic is the same as the recursive approach, but we just use some extra pointers to do the swapping of nodes. 

Implementation in C++

// C++ code to flip binary tree
#include <bits/stdc++.h>
using namespace std;
// binary tree class
class BinaryTreeNode
{
public:
    int val;
    BinaryTreeNode *left, *right;
    // constructor
    BinaryTreeNode(int val)
    {
        this->val = val;
        this->left = NULL;
        this->right = NULL;
    }
};
BinaryTreeNode *FlipBinaryTree(BinaryTreeNode *root)
{
    // intiliazing the pointers to do the swapping and storing states
    BinaryTreeNode *curr = root, *next = NULL, *prev = NULL, *temp = NULL;
    while (curr != NULL)
    {
        // pointing the next pointer to the current next of left
        next = curr->left;
        // making the right child of prev as curr left child
        curr->left = temp;

        // storign the right child of curr in temp
        temp = curr->right;

        curr->right = prev;
        prev = curr;
        curr = next;
    }
    return prev;
}
void LevelOrderTraversal(BinaryTreeNode *root)
{
    // initiliazing the queue to do the level order traversal
    queue<BinaryTreeNode *> q;
    // pushing the root into the queue
    q.push(root);
    while (!q.empty())
    {
        int len = q.size();
        while (len--)
        {
            BinaryTreeNode *node = q.front();
            q.pop();
            if (node->left)
            {
                q.push(node->left);
            }
            if (node->right)
            {
                q.push(node->right);
            }
            cout << node->val << " ";
        }
        cout << endl;
    }
}
int main()
{
    // building the binary tree
    BinaryTreeNode *root = new BinaryTreeNode(50);
    
    root->left = new BinaryTreeNode(20);
    root->right = new BinaryTreeNode(40);

    // printing the binary tree before calling the flip binary tree function
    cout << "Printing before calling the FlipBinaryTree function" << endl;
    
    LevelOrderTraversal(root);
    
    root = FlipBinaryTree(root);
    
    // printing the binary tree after calling the flip binary tree function
    cout << "Printing after calling the FlipBinaryTree function" << endl;
    LevelOrderTraversal(root);
    cout << endl;
}

 

Output:

Printing before calling the FlipBinaryTree function
50
20 40
Printing after calling the FlipBinaryTree function
20
40 50

 

Complexity Analysis

Time Complexity: O(N)

We are only doing linear traversal of the tree, so only linear time complexity. 

Space Complexity: O(1)

We are not taking any extra space to flip the binary tree. 

Frequently Asked Questions

What are tree traversals?  

When traversing a tree, the value of each node is visited and output in a specific order. This tutorial will use the Inorder, Preorder, and Postorder tree traversal methods.

In contrast to linear data structures such as arrays, bitmaps, and matrices, where traversal is done in a linear order, tree traversal is important because there are various ways to carry out traversal operations.

Each of these ways of traversing a tree follows a specific order:

  • In order, you traverse from the left subtree to the root, then to the right subtree.
  • You go from the root to the left subtree, then to the right subtree for Preorder.
  • You travel from the left subtree to the right subtree, then back to the left subtree for Post order.

What is the difference between Breadth-first Search and Depth-first search? 

The BFS uses queue data structure while DFS uses the stack data structure. BFS is more suitable for searching vertices closer to the given source, while DFS is more suitable for solutions away from the source.

What is the difference between a binary tree and a binary search tree?

A tree that has a maximum of 2 children is called a binary tree, whereas a binary search tree is a particular binary tree having the following properties. 

Keys in the left subtree are always smaller than the root's node, whereas keys in the right subtree are greater than the root's node. 

What is the binary heap? 

A Binary Heap is a Binary Tree that possesses the following characteristics:

  • It's a full-fledged tree (all levels are filled except possibly the last level and the last level has all keys as left as possible). Because of this trait, Binary Heap can be stored in an array.
  • It's either a Min Heap or a Max Heap in a Binary Heap. In a Min Binary Heap, the root key must be the smallest of all the keys in the Binary Heap. The same property must be true recursively for all nodes in a Binary Tree. MinHeap is comparable to Max Binary Heap.

Conclusion 

In this article, we discussed an interesting problem: we are given a binary tree, and we need to flip the binary tree in the right direction that is in a clockwise direction. I hope you have understood the recursive as well as iterative approaches.

Recommended problems -

 

Refer to our Guided Path on Coding Ninjas Studio to upskill yourself in Data Structures and AlgorithmsCompetitive ProgrammingJavaScriptSystem DesignMachine learning, and many more! If you want to test your competency in coding, you may check out the mock test series and participate in the contests hosted on Coding Ninjas Studio! But if you have just started your learning process and are looking for questions asked by tech giants like Amazon, Microsoft, Uber, etc; you must look at the problemsinterview experiences, and interview bundle for placement preparations.

Nevertheless, you may consider our paid courses to give your career an edge over others!

Do upvote our blogs if you find them helpful and engaging!

Happy Learning!!