Remove all nodes which lie on path having sum less than k
Given a binary tree, remove all nodes which lie on path having sum less than k. For example, consider the following binary tree
If k=4, after removing all nodes which lie on path having sum less than 4, tree looks like
If k=23, after removing all nodes which lie on path having sum less than 23, tree looks like
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.
It is recommended to go through Post-order Traversal of a binary tree first because deleting nodes of a binary tree is done in bottom-up manner by first deleting children and then parent. While traversing down we pass sum as a parameter which is the sum of all the nodes on the current path including the current node. Recursively traverse left and right subtrees passing the sum. Once we reach a leaf node, we check if its path sum is less than k. If it is, then return null. While backtracking from recursive steps, find maximum of left and right path sum. If the maximum sum becomes less than k, then we delete the current node by setting it to null. Please note that by the time we come to delete a node, its children would have already been deleted and hence the current node which we will be deleting will be a leaf node.
Support us by whitelisting IDeserve in your ad-blocker.