Invert a Binary Tree
You are provided with a Binary Tree and one of its leaf nodes. You have to invert this binary tree. Inversion must be done by following all the below guidelines:

• The given leaf node becomes the root after the inversion. • For a node (say, ‘x’) ○ If there exists the left child that is not yet taken then this child must become the right child of ‘x’. ○ If the left child is already taken then the right child is still on the right side of ‘x’. • The parent of ‘x’ must be the left child of ‘x’.

For Example:

Consider the above binary tree (image- before inversion), if the given leaf node is ‘1’ then the binary tree after inversion becomes exactly the same as given in the image representing after inversion.

Note:

The given binary tree will only have distinct values of nodes.

Input Format:

The first line contains a single integer ‘T’ representing the number of test cases. The first line of each test case will contain a single TreeNode “leaf” which denotes one of the leaf nodes of the given binary tree. The second line of each test case contains elements of the tree in the level order form. The line consists of values of nodes separated by a single space. In case a node is null, we take -1 in its place. For example, the input for the tree depicted in the below image would be :

1 2 3 4 -1 5 6 -1 7 -1 -1 -1 -1 -1 -1

Explanation :

Level 1 : The root node of the tree is 1 Level 2 : Left child of 1 = 2 Right child of 1 = 3 Level 3 : Left child of 2 = 4 Right child of 2 = null (-1) Left child of 3 = 5 Right child of 3 = 6 Level 4 : Left child of 4 = null (-1) Right child of 4 = 7 Left child of 5 = null (-1) Right child of 5 = null (-1) Left child of 6 = null (-1) Right child of 6 = null (-1) Level 5 : Left child of 7 = null (-1) Right child of 7 = null (-1) The first not-null node(of the previous level) is treated as the parent of the first two nodes of the current level. The second not-null node (of the previous level) is treated as the parent node for the next two nodes of the current level and so on. The input ends when all nodes at the last level are null(-1).

Note :

The above format was just to provide clarity on how the input is formed for a given tree. The sequence will be put together in a single line separated by a single space. Hence, for the above-depicted tree, the input will be given as: 1 2 3 4 -1 5 6 -1 7 -1 -1 -1 -1 -1 -1

Output Format:

For each test case, return the whole binary tree (according to the format as it has been given in the input) after considering the given leaf node as the new root node. Output for every test case will be printed in a separate line.

Note:

You don’t need to print anything; It has already been taken care of. Just implement the given function.

Constraints:

1

Question

Invert a Binary Tree

You are provided with a Binary Tree and one of its leaf nodes. You have to invert this binary tree. Inversion must be done by following all the below guidelines:

• The given leaf node becomes the root after the inversion.

• For a node (say, ‘x’) 
    ○ If there exists the left child that is not yet taken then this child must become the right child of ‘x’.
    ○ If the left child is already taken then the right child is still on the right side of ‘x’.

• The parent of ‘x’ must be the left child of ‘x’.

For Example:

Example-img01
Example-img02

Consider the above binary tree (image- before inversion), if the given leaf node is ‘1’ then the binary tree after inversion becomes exactly the same as given in the image representing after inversion.

Note:

The given binary tree will only have distinct values of nodes.

Input Format:

The first line contains a single integer ‘T’ representing the number of test cases. 

The first line of each test case will contain a single TreeNode “leaf” which denotes one of the leaf nodes of the given binary tree.

The second line of each test case contains elements of the tree in the level order form. The line consists of values of nodes separated by a single space. In case a node is null, we take -1 in its place.

For example, the input for the tree depicted in the below image would be :

Example

1
2 3
4 -1 5 6
-1 7 -1 -1 -1 -1
-1 -1

Explanation :

Level 1 :
The root node of the tree is 1

Level 2 :
Left child of 1 = 2
Right child of 1 = 3

Level 3 :
Left child of 2 = 4
Right child of 2 = null (-1)
Left child of 3 = 5
Right child of 3 = 6

Level 4 :
Left child of 4 = null (-1)
Right child of 4 = 7
Left child of 5 = null (-1)
Right child of 5 = null (-1)
Left child of 6 = null (-1)
Right child of 6 = null (-1)

Level 5 :
Left child of 7 = null (-1)
Right child of 7 = null (-1)

The first not-null node(of the previous level) is treated as the parent of the first two nodes of the current level. The second not-null node (of the previous level) is treated as the parent node for the next two nodes of the current level and so on.
The input ends when all nodes at the last level are null(-1).

Note :

The above format was just to provide clarity on how the input is formed for a given tree. 
The sequence will be put together in a single line separated by a single space. Hence, for the above-depicted tree, the input will be given as:

1 2 3 4 -1 5 6 -1 7 -1 -1 -1 -1 -1 -1

Output Format:

For each test case, return the whole binary tree (according to the format as it has been given in the input) after considering the given leaf node as the new root node.

Output for every test case will be printed in a separate line.

Note:

You don’t need to print anything; It has already been taken care of. Just implement the given function.

Constraints:

1 <= T <= 50
1 <= N <= 10000
-10^5 <= DATA <= 10^5
Leaf is one of the leaf nodes of the given binary tree.

Time limit: 1 sec

Accepted Answer

I explained the approach of swaping the child two nodes while traversing each node. The interview was fine with that approach

Accepted Answer

In-order Traversal

The basic idea is to first fill all the nodes (in a stack) that are present in a path whose leaf node is the given leaf node using In-order traversal. And, then keep removing nodes from the stack and attaching with the given leaf node according to the given guidelines.

We are using a helper function that takes the root of the given binary tree, a stack, and the given leaf node as input and returns a boolean that denotes whether this path includes the given leaf node or not (true if includes, otherwise false).

bool helper(TreeNode *root, stack *> &st, TreeNode *leaf)

Where “ROOT” is the root of the given binary tree, “ST” is the stack that holds nodes present in the current path, and “LEAF” is the given leaf node.

The steps are as follows:

In the “HELPER” function
- Push the “ROOT” into the “ST”.
- Check if the “ROOT” is a leaf Node.
  - Now, if “ROOT” is the given leaf node i.e “LEAF” then return true.
  - Else, pop out the node stored at the top of “ST” and return false.
- Make a recursive call for the left subtree and if the result obtained is true then return true.
- Similarly, do for the left subtree.
- Pop-out the node stored at the top of “ST” and return false.
In the given function
- Check if the “ROOT” is NULL then return “ROOT”.
- Make a stack named “ST” to store the nodes present in the current path.
- Call the “HELPER” function by passing arguments as “ROOT”, “ST”, and “LEAF”.
- Create a node named “NEW_ROOT” which holds the new root of the given binary tree. Set “NEW_ROOT” to the node stored at the top of “ST”.
- Pop-out the node stored at the top of “ST”.
- Create another node named “PARENT” that will hold the parent node. Initially set “PARENT” equal to “NEW_ROOT”.
- Iterate while “ST” is not empty.
  - Pop-out the top node of “ST” and store in a node named “CUR_NODE”.
  - Now, check if the left of the “CUR_NODE” is “PARENT” then just set its left NULL and assign it to the left of “PARENT”.
  - Else, make its right child to its left child and then set the left child as NULL. And, finally, make this “CUR_NODE” the left child of “PARENT”.
  - Move “PARENT” ahead.
- Return “NEW_ROOT”.

Space Complexity: O(n)Explanation:

O(N), where ‘N’ is the total number of coins.

Since we are using extra space in the form of a stack that can take O(N) space in case of a skewed tree and so, the overall space complexity will be O(N).

Time Complexity: O(n)Explanation:

O(N), where ‘N’ is the total number of nodes in the given binary tree.

Since in the “helper” function we are just traversing each node (takes O(N) time) and in the main function we are just removing every node that is stored in the stack that might go up to N in case of the skewed tree (takes O(N) time) and so the overall time complexity will be O(N).

Python (3.5)

'''
	Time complexity: O(N) 
	Space complexity: O(N)
	
	Where 'N' is the number of nodes in the given binary tree.
'''

from collections import deque

def helper(root, st, leaf):
    
    # Push the current node i.e "root" into the stack.
    st.append(root)
    
    # Check if it is a leaf node of the given binary tree.
    if root.left == None and root.right == None:
        # Check if this leaf is the given leaf node then return true.
        if root.data == leaf:
            return True
            
        # Else, pop-out the current node from the stack and then return false.
        else:
            st.pop()
            return False
            
    # Variables to store the result obtained from left and right subtree calls.
    left = False
    right = False
    
    # Call for the left subtree, if there exists left child.
    if root.left != None:
        left = helper(root.left, st, leaf)
        
    # If found the required path then return true.
    if left:
        return True
        
        
    # Call for the right subtree, if there exists right child.
    if root.right != None:
        right = helper(root.right, st, leaf)
        
    # If found the required path then return true.
    if right:
        return True
        
    # Otherwise, pop-out the current node from the stack and then return false.
    st.pop()
    return False
    

def invertBinaryTree(root, leaf):
    
    # If the root is null then return root itself.
    if root == None:
        return root
        
        
    # Stack that will store the path which includes the given leaf node.
    st = deque()
    
    # Call the helper function.
    helper(root, st, leaf)
    
    # Node that holds the new Root i.e. the given leaf node.
    
    newRoot = st.pop()
    #  Node that stores the parent of the current node while inverting the given binary tree.
    parent = newRoot
    
    while len(st) > 0:
        # Node that stores the current node.
        curNode = st.pop()
        
        if curNode.left == parent:
            curNode.left = None
            parent.left = curNode
            
        else:
            curNode.right = curNode.left
            curNode.left = None
            parent.left = curNode
            
        parent = parent.left
        
    return newRoot

Java (SE 1.8)

/*

	Time complexity: O(N) 

	Space complexity: O(N)

	

	Where 'N' is the number of nodes in the given binary tree.

*/





import java.util.Stack;



public class Solution {



	// Function which helps in filling the required path in the stack.

	private static boolean helper(TreeNode root, Stack> st, TreeNode leaf) {

		// Push the current node i.e "root" into the stack.

		st.push(root);

	

		// Check if it is a leaf node of the given binary tree.

		if (root.left == null && root.right == null) {

			// Check if this leaf is the given leaf node then return true.

			if (root.data.intValue() == leaf.data.intValue()) {

				return true;

			}

			// Else, pop-out the current node from the stack and then return false.

			else {

				st.pop();

				return false;

			}

		}



		// Variables to store the result obtained from left and right subtree calls.

		boolean left = false, right = false;



		// Call for the left subtree, if there exists left child.

		if (root.left != null) {

			left = helper(root.left, st, leaf);

		}

		// If found the required path then return true.

		if (left) {

			return true;

		}



		// Call for the right subtree, if there exists right child.

		if (root.right != null) {

			right = helper(root.right, st, leaf);

		}

		// If found the required path then return true.

		if (right) {

			return true;

		}



		// Otherwise, pop-out the current node from the stack and then return false.

		st.pop();

		return false;

	}



	public static TreeNode invertBinaryTree(TreeNode root, TreeNode leaf) {

		// If the root is null then return root itself.

		if (root == null) {

			return root;

		}



		// Stack that will store the path which includes the given leaf node.

		Stack> st = new Stack>();



		// Call the helper function.

		helper(root, st, leaf);

		// System.out.println(st.size());

		// Node that holds the new Root i.e. the given leaf node.



		

		TreeNode newRoot = st.peek();

		st.pop();



		// Node that stores the parent of the current node while inverting the given

		// binary tree.

		TreeNode parent = newRoot;



		while (!st.isEmpty()) {

			// Node that stores the current node.

			TreeNode curNode = st.peek();

			st.pop();



			if (curNode.left == parent) {

				curNode.left = null;

				parent.left = curNode;

			} else {

				curNode.right = curNode.left;

				curNode.left = null;

				parent.left = curNode;

			}



			parent = parent.left;

		}



		return newRoot;

	}

}

C++ (g++ 5.4)

/*

	Time complexity: O(N) 

	Space complexity: O(N)

	

	Where 'N' is the number of nodes in the given binary tree.

*/



//  Function which helps in filling the required path in the stack.

bool helper(TreeNode *root, stack *> &st, TreeNode *leaf)

{

    // Push the current node i.e "root" into the stack.

    st.push(root);



    // Check if it is a leaf node of the given binary tree.

    if (root->left == NULL && root->right == NULL)

    {

        // Check if this leaf is the given leaf node then return true.

        if (root->data == leaf->data)

        {

            return true;

        }

        // Else, pop-out the current node from the stack and then return false.

        else

        {

            st.pop();

            return false;

        }

    }

    

    // Variables to store the result obtained from left and right subtree calls.

    bool left = false, right = false;



    // Call for the left subtree, if there exists left child.

    if(root->left!=NULL){

        left = helper(root->left, st, leaf);

    }

    // If found the required path then return true.

    if (left)

    {

        return true;

    }



    // Call for the right subtree, if there exists right child.

    if(root->right!=NULL){

        right = helper(root->right, st, leaf);

    }

    // If found the required path then return true.

    if (right)

    {

        return true;

    }



    // Otherwise, pop-out the current node from the stack and then return false.

    st.pop();

    return false;

}



TreeNode *invertBinaryTree(TreeNode *root, TreeNode *leaf)

{

    // If the root is NULL then return root itself.

    if (root == NULL)

    {

        return root;

    }



    // Stack that will store the path which includes the given leaf node.

    stack *> st;



    // Call the helper function.

    helper(root, st, leaf);



    // Node that holds the new Root i.e. the given leaf node.

    TreeNode *newRoot = st.top();

    st.pop();



    // Node that stores the parent of the current node while inverting the given binary tree.

    TreeNode *parent = newRoot;



    while (!st.empty())

    {

        // Node that stores the current node.

        TreeNode *curNode = st.top();

        st.pop();



        if (curNode->left == parent)

        {

            curNode->left = NULL;

            parent->left = curNode;

        }

        else

        {

            curNode->right = curNode->left;

            curNode->left = NULL;

            parent->left = curNode;

        }



        parent = parent->left;

    }



    return newRoot;

}

You are provided with a Binary Tree and one of its leaf nodes. You have to invert this binary tree. Inversion must be done by following all the below guidelines:

For Example:

Note:

Input Format:

Explanation :

Note :

Output Format:

Note:

Constraints:

Top Freshworks Graduate Trainee interview questions & answers

Popular interview questions of Graduate Trainee