Remove Half Nodes

Easy
0/40
Average time to solve is 15m
profile
Contributed by
2 upvotes
Asked in companies
ShareChatAmazon

Problem statement

You are given a binary tree consisting of ‘N’ nodes. Your task is to replace all the half nodes present in the binary tree with its child node. Half nodes are those nodes that have only one child.

For Example:

In this given binary tree, nodes 7, 5, and 9 are half nodes because they have only one child node. So we have to replace these nodes with their child. The inorder traversal of the updated binary tree is [1, 6, 11, 2, 4]. Hence, the answer is [1, 6, 11, 2, 4].

undirected

Example: 
Elements are in the level order form. The input consists of values of nodes separated by a single space in a single line. 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 :

undirected 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
Detailed explanation ( Input/output format, Notes, Images )
Input format : 
The first line contains a single integer ‘T’, representing the number of test cases.

The first line of each test case contains space-separated integers representing the level order traversal of the binary tree. If any node does not have a left or right child, take -1 in place of the child.
Output format : 
For each test case, print the inorder traversal of the updated tree in a space-separated manner.

Print the output of each test case in a separate line.
Note: 
You do not need to print anything. It has already been taken care of. Just implement the given function.
Constraints: 
1 <= ‘T’ <= 5
1 <= ‘N’ <= 10^5
1 <= nodeVal <= 10^12

Time Limit: 1 sec
Sample Input 1:
2
7 12 8 2 -1 -1 -1 -1 -1
1 2 3 -1 4 -1 7 5 6 8 -1 -1 -1 -1 -1 -1 -1
Sample Output 1:
2 7 8
5 4 6 1 8
Explanation:
In test case 1: 
In the given binary tree, node 12 is the half node because it has only one child. So we have to replace that node with their child. The inorder traversal of the updated binary tree is [2, 7, 8]. Hence, the answer is [2, 7, 8].

In test case 2: 
In the given binary tree, nodes 2, 3, and 7 are the half nodes because they have only one child. So we have to replace these nodes with their child. The inorder traversal of the updated binary tree is [5, 4, 6, 1, 8]. Hence, the answer is [5, 4, 6, 1, 8].
Sample Input 2:
2
1 -1 5 -1 7 -1 9 -1 -1
2 7 5 -1 9 -1 1 11 4 -1 -1 -1 -1 -1 -1
Sample Output 2:
9    
11 9 4 2 1
Hint

Try to think of a Depth First Search approach.

Approaches (2)
Depth First Search

In this approach, we will traverse the tree in Depth First Search. We will make a recursive function removeHalfNodes(root). The base condition is if the root is an empty node, then we will return an empty node. We will make the recursive call on the left and right children to traverse on the left and right subtree. The conditions to find the half nodes are-: 

  1. If both left and right child nodes of root are empty nodes, this node is a leaf node.
  2. If the left child of the root node is an empty node, this node is a half node and will update the root as the root’s right child.
  3. If the right child of the root node is an empty node, this node is a half node and will update the root as the root’s left child.

In the end, we will return the updated root node.

 

Algorithm:

  • Make a recursive function removeHalfNodes(root) where the root is the root node of the given binary tree. This function returns the root node of the updated binary tree.
    • The base condition of this function is if the root is an empty node, then we will return an empty node.
    • Set the left child of the root as the node returned by removeHalfNodes( left child of the root ).
    • Set the right child of the root as the node returned by removeHalfNodes(right child of the root).
    • If the left child of root is the empty node and the right child of root is a non-empty node, then.
      • Set newRoot as the root node.
      • Set root as the right child of the root.
      • Delete the newRoot.
    • If the right child of root is the empty node and the left child of root is a non-empty node, then
      • Set newRoot as the root node.
      • Set root as the left child of the root.
      • Delete the newRoot.
    • Return the root node.
Time Complexity

O(N) where N is the number of nodes in the given binary tree.

 

We are traversing each node recursively only once, which takes O(N) time. Hence, the overall time complexity is O(N).

Space Complexity

O(N) where N is the number of nodes in the given binary tree.

 

The space complexity O(N) is used for the recursion stack in the worst case. Hence, the overall space complexity is O(N).

Code Solution
(100% EXP penalty)
Remove Half Nodes
Full screen
Console