Last Updated: 7 Dec, 2020

Remove Half Nodes

Easy

Asked in companies

Solve now

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

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

Solve now

Approaches

01 Approach

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-:

If both left and right child nodes of root are empty nodes, this node is a leaf node.
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.
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.

Solve now

02 Approach

In this approach, we will traverse the tree in Breadth-First Search. In this, we will maintain a queue q to store the traversal order and a HashMap hm that stores the parent node corresponding to each child node. For each node, we have to check whether the node is a half node or not. If it is the half node, we have to update its parent node, which we can get from the HashMap. In the end, we will return the updated root node.

Algorithm:

Maintain a HashMap hm that stores the parent node corresponding to the child node.
Maintain a queue q to store the order of traversal.
Make the parent of the root as an empty node in hm.
Insert root node in the queue q.
Iterate while q is not empty.
- Set frontNode as a front node of queue q.
- Delete the front element of the queue.
- If frontNode has both left and right child:
  - Set frontNode as a parent of the left child in HashMap hm.
  - Set frontNode as a parent of the right child in HashMap hm.
  - Insert left child in the queue.
  - Insert the right child in the queue.
- Otherwise, if frontNode has an only left child:
  - Check If hm[frontNode] is an empty node.
    - Set root as the left child of frontNode.
    - Make the parent of the left child of frontNode as an empty node in hm.
  - If hm[frontNode] is not an empty node.
    - If frontNode is the left child of its parent, then set left child of the parent of frontNode as the left child of frontNode
    - Otherwise, if frontNode is the right child of its parent, then set right child of the parent of frontNode as the left child of frontNode
    - Set parent of the left child of frontNode as a parent of frontNode in HashMap hm.
  - Insert left child of frontNode in the queue
- Otherwise, if frontNode has an only right child:
  - Check If hm[frontNode] is an empty node.
    - Set root as the right child of frontNode.
    - Make the parent of the right child of frontNode as empty in hm.
  - If hm[frontNode] is not an empty node.
    - If frontNode is the left child of its parent, then set the left child of the parent of frontNode as the right child of frontNode.
    - Otherwise, frontNode is the right child of its parent, then set right child of the parent of frontNode as the right child of frontNode.
    - Set parent of right child of frontNode as the parent of frontNode in HashMap hm.
  - Insert the right child of frontNode in the queue.
Return root, which is the updated root of the binary tree.

Solve now