Remove all the half nodes from a given binary tree
Given a binary tree, write a program to remove all the half nodes from it. For example, in the following binary tree, nodes 3,6,2,5 are half nodes.
and removing them results in the following binary tree.
Our program should return the root of the modified binary tree. Note that leaf nodes have both children as null and therefore they should not be removed.
Video coming soon!
Subscribe for more updates
Preparing for interviews? IDeserve team is here to help.
Create your profile
Create your profile, and here is what you will get:
1: Interview practice platform.
2: Once you are ready to take the interview, IDeserve team will help you get connected to the best job opportunities.
3: Personalized mentorship from IDeserve team once your interview process has started.
Creation of profile shouldn't take more than 2 minutes.
The algorithm uses bottom-up approach to delete the half nodes from the given binary tree. It uses post-order traversal - when first removeHalfNodes(TreeNode currentNode) call is made with currentNode as root of the binary tree, the function uses following steps.
1. If currentNode is null return null since this is a empty tree. This is the base case for this recursive algorithm. 2. Remove all the half nodes from currentNode's left sub-tree and make currentNode'e left child point to this modified left sub-tree. This is done using recursive call - currentNode.left = removeHalfNodes(currentNode.left). 3. Remove all the half nodes from currentNode's right sub-tree and make currentNode'e right child point to this modified right sub-tree. This is done using recursive call - currentNode.right = removeHalfNodes(currentNode.right). 4. Finally when left and right sub-trees are modified for currentNode, check if currentNode's left child is null with right child being non-null value. If this is the case then we need to delete currentNode. We do that by returning currentNode's right child to its parent and making currentNode as null. 5. Similarly, if currentNode's right child is null with left child being a non-null value, we need to delete currentNode. We do that by returning currentNode's left child to its parent and making currentNode as null.
In the above tree when currentNode is 6, it returns reference of node 8 to its parent that is node 3 makes reference of itself as null. Modified tree looks like following tree.
Then again when currentNode is node 3, it again returns reference of node 8 to its parent that is node 1 and modified tree looks like following.
Since this is essentially a post-order traversal, time taken is O(n) and extra space taken is O(1).
Support us by whitelisting IDeserve in your ad-blocker.