Remove all nodes which don’t lie in any path with sum>= k

Last Updated : 04 Apr, 2023

Given a binary tree, a complete path is defined as a path from root to a leaf. The sum of all nodes on that path is defined as the sum of that path. Given a number K, you have to remove (prune the tree) all nodes which don’t lie in any path with sum>=k.

Note: A node can be part of multiple paths. So we have to delete it only in case when all paths from it have sum less than K.

Consider the following Binary Tree
          1 
      /      \
     2        3
   /   \     /  \
  4     5   6    7
 / \    /       /
8   9  12      10
   / \           \
  13  14         11
      / 
     15 

For input k = 20, the tree should be changed to following
(Nodes with values 6 and 8 are deleted)
          1 
      /      \
     2        3
   /   \        \
  4     5        7
   \    /       /
    9  12      10
   / \           \
  13  14         11
      / 
     15 

For input k = 45, the tree should be changed to following.
      1 
    / 
   2   
  / 
 4  
  \   
   9    
    \   
     14 
     /
    15

Recommended: Please solve it on “PRACTICE” first, before moving on to the solution.

The idea is to traverse the tree and delete nodes in bottom up manner. While traversing the tree, recursively calculate the sum of nodes from root to leaf node of each path. For each visited node, check the total calculated sum against given sum “k”. If sum is less than k, then free(delete) that node (leaf node) and return the sum back to the previous node. Since the path is from root to leaf and nodes are deleted in bottom up manner, a node is deleted only when all of its descendants are deleted. Therefore, when a node is deleted, it must be a leaf in the current Binary Tree.

Following is the implementation of the above approach.

C++

#include <bits/stdc++.h>
using namespace std;
 
// A utility function to get maximum of two integers
int max(int l, int r) { return (l > r ? l : r); }
 
// A Binary Tree Node
struct Node
{
    int data;
    struct Node *left, *right;
};
 
// A utility function to create a new Binary Tree node with given data
struct Node* newNode(int data)
{
    struct Node* node = (struct Node*) malloc(sizeof(struct Node));
    node->data = data;
    node->left = node->right = NULL;
    return node;
}
 
// print the tree in LVR (Inorder traversal) way.
void print(struct Node *root)
{
    if (root != NULL)
    {
        print(root->left);
        cout <<" "<< root->data;
        print(root->right);
    }
}
 
/* Main function which truncates the binary tree. */
struct Node *pruneUtil(struct Node *root, int k, int *sum)
{
    // Base Case
    if (root == NULL)  return NULL;
 
    // Initialize left and right sums as sum from root to
    // this node (including this node)
    int lsum = *sum + (root->data);
    int rsum = lsum;
 
    // Recursively prune left and right subtrees
    root->left = pruneUtil(root->left, k, &lsum);
    root->right = pruneUtil(root->right, k, &rsum);
 
    // Get the maximum of left and right sums
    *sum = max(lsum, rsum);
 
    // If maximum is smaller than k, then this node
    // must be deleted
    if (*sum < k)
    {
        free(root);
        root = NULL;
    }
 
    return root;
}
 
// A wrapper over pruneUtil()
struct Node *prune(struct Node *root, int k)
{
    int sum = 0;
    return pruneUtil(root, k, &sum);
}
 
// Driver program to test above function
int main()
{
    int k = 45;
    struct Node *root = newNode(1);
    root->left = newNode(2);
    root->right = newNode(3);
    root->left->left = newNode(4);
    root->left->right = newNode(5);
    root->right->left = newNode(6);
    root->right->right = newNode(7);
    root->left->left->left = newNode(8);
    root->left->left->right = newNode(9);
    root->left->right->left = newNode(12);
    root->right->right->left = newNode(10);
    root->right->right->left->right = newNode(11);
    root->left->left->right->left = newNode(13);
    root->left->left->right->right = newNode(14);
    root->left->left->right->right->left = newNode(15);
 
    cout <<"Tree before truncation\n";
    print(root);
 
    root = prune(root, k); // k is 45
 
    cout <<"\n\nTree after truncation\n";
    print(root);
 
    return 0;
}
 
// This code is contributed by shivanisinghss2110

C

#include <stdio.h>
#include <stdlib.h>
 
// A utility function to get maximum of two integers
int max(int l, int r) { return (l > r ? l : r); }
 
// A Binary Tree Node
struct Node
{
    int data;
    struct Node *left, *right;
};
 
// A utility function to create a new Binary Tree node with given data
struct Node* newNode(int data)
{
    struct Node* node = (struct Node*) malloc(sizeof(struct Node));
    node->data = data;
    node->left = node->right = NULL;
    return node;
}
 
// print the tree in LVR (Inorder traversal) way.
void print(struct Node *root)
{
    if (root != NULL)
    {
        print(root->left);
        printf("%d ",root->data);
        print(root->right);
    }
}
 
/* Main function which truncates the binary tree. */
struct Node *pruneUtil(struct Node *root, int k, int *sum)
{
    // Base Case
    if (root == NULL)  return NULL;
 
    // Initialize left and right sums as sum from root to
    // this node (including this node)
    int lsum = *sum + (root->data);
    int rsum = lsum;
 
    // Recursively prune left and right subtrees
    root->left = pruneUtil(root->left, k, &lsum);
    root->right = pruneUtil(root->right, k, &rsum);
 
    // Get the maximum of left and right sums
    *sum = max(lsum, rsum);
 
    // If maximum is smaller than k, then this node
    // must be deleted
    if (*sum < k)
    {
        free(root);
        root = NULL;
    }
 
    return root;
}
 
// A wrapper over pruneUtil()
struct Node *prune(struct Node *root, int k)
{
    int sum = 0;
    return pruneUtil(root, k, &sum);
}
 
// Driver program to test above function
int main()
{
    int k = 45;
    struct Node *root = newNode(1);
    root->left = newNode(2);
    root->right = newNode(3);
    root->left->left = newNode(4);
    root->left->right = newNode(5);
    root->right->left = newNode(6);
    root->right->right = newNode(7);
    root->left->left->left = newNode(8);
    root->left->left->right = newNode(9);
    root->left->right->left = newNode(12);
    root->right->right->left = newNode(10);
    root->right->right->left->right = newNode(11);
    root->left->left->right->left = newNode(13);
    root->left->left->right->right = newNode(14);
    root->left->left->right->right->left = newNode(15);
 
    printf("Tree before truncation\n");
    print(root);
 
    root = prune(root, k); // k is 45
 
    printf("\n\nTree after truncation\n");
    print(root);
 
    return 0;
}

Java

// Java program to implement
// the above approach
import java.util.*; 
class GFG
{
 
// A utility function to get
// maximum of two integers 
static int max(int l, int r) 
{ 
    return (l > r ? l : r);
} 
 
// A Binary Tree Node 
static class Node 
{ 
    int data; 
    Node left, right; 
}; 
 
static class INT
{
    int v;
INT(int a)
{
    v = a;
}
}
 
// A utility function to create 
// a new Binary Tree node with
// given data 
static Node newNode(int data) 
{ 
    Node node = new Node(); 
    node.data = data; 
    node.left = node.right = null; 
    return node; 
} 
 
// print the tree in LVR 
// (Inorder traversal) way. 
static void print(Node root) 
{ 
    if (root != null) 
    { 
        print(root.left); 
        System.out.print(root.data + " "); 
        print(root.right); 
    } 
} 
 
// Main function which
// truncates the binary tree. 
static Node pruneUtil(Node root, int k, 
                      INT sum) 
{ 
    // Base Case 
    if (root == null) return null; 
 
    // Initialize left and right 
    // sums as sum from root to 
    // this node (including this node) 
    INT lsum = new INT(sum.v + (root.data)); 
    INT rsum = new INT(lsum.v); 
 
    // Recursively prune left 
    // and right subtrees 
    root.left = pruneUtil(root.left, k, lsum); 
    root.right = pruneUtil(root.right, k, rsum); 
 
    // Get the maximum of
    // left and right sums 
    sum.v = max(lsum.v, rsum.v); 
 
    // If maximum is smaller 
    // than k, then this node 
    // must be deleted 
    if (sum.v < k) 
    { 
 
        root = null; 
    } 
 
    return root; 
} 
 
// A wrapper over pruneUtil() 
static Node prune(Node root, int k) 
{ 
    INT sum = new INT(0); 
    return pruneUtil(root, k, sum); 
} 
 
// Driver Code
public static void main(String args[])
{ 
    int k = 45; 
    Node root = newNode(1); 
    root.left = newNode(2); 
    root.right = newNode(3); 
    root.left.left = newNode(4); 
    root.left.right = newNode(5); 
    root.right.left = newNode(6); 
    root.right.right = newNode(7); 
    root.left.left.left = newNode(8); 
    root.left.left.right = newNode(9); 
    root.left.right.left = newNode(12); 
    root.right.right.left = newNode(10); 
    root.right.right.left.right = newNode(11); 
    root.left.left.right.left = newNode(13); 
    root.left.left.right.right = newNode(14); 
    root.left.left.right.right.left = newNode(15); 
 
    System.out.println("Tree before truncation\n"); 
    print(root); 
 
    root = prune(root, k); // k is 45 
 
    System.out.println("\n\nTree after truncation\n"); 
    print(root); 
} 
}
 
// This code is contributed by Arnab Kundu

Python3

# A class to create a new Binary Tree
# node with given data 
class newNode:
    def __init__(self, data): 
        self.data = data 
        self.left = self.right = None
 
# print the tree in LVR (Inorder traversal) way. 
def Print(root):
    if (root != None):
        Print(root.left) 
        print(root.data, end = " ") 
        Print(root.right)
 
# Main function which truncates
# the binary tree. 
def pruneUtil(root, k, Sum):
     
    # Base Case 
    if (root == None):
        return None
 
    # Initialize left and right Sums as 
    # Sum from root to this node 
    # (including this node) 
    lSum = [Sum[0] + (root.data)] 
    rSum = [lSum[0]] 
 
    # Recursively prune left and right 
    # subtrees 
    root.left = pruneUtil(root.left, k, lSum) 
    root.right = pruneUtil(root.right, k, rSum) 
 
    # Get the maximum of left and right Sums 
    Sum[0] = max(lSum[0], rSum[0]) 
 
    # If maximum is smaller than k, 
    # then this node must be deleted 
    if (Sum[0] < k[0]):
        root = None
    return root
 
# A wrapper over pruneUtil() 
def prune(root, k):
    Sum = [0] 
    return pruneUtil(root, k, Sum)
 
# Driver Code
if __name__ == '__main__':
    k = [45]
    root = newNode(1) 
    root.left = newNode(2) 
    root.right = newNode(3) 
    root.left.left = newNode(4) 
    root.left.right = newNode(5) 
    root.right.left = newNode(6) 
    root.right.right = newNode(7) 
    root.left.left.left = newNode(8) 
    root.left.left.right = newNode(9) 
    root.left.right.left = newNode(12) 
    root.right.right.left = newNode(10) 
    root.right.right.left.right = newNode(11) 
    root.left.left.right.left = newNode(13) 
    root.left.left.right.right = newNode(14) 
    root.left.left.right.right.left = newNode(15) 
 
    print("Tree before truncation")
    Print(root) 
    print()
    root = prune(root, k) # k is 45 
 
    print("Tree after truncation")
    Print(root)
 
# This code is contributed by PranchalK

C#

using System;
 
// C# program to implement 
// the above approach 
public class GFG
{
 
// A utility function to get 
// maximum of two integers  
public static int max(int l, int r)
{
    return (l > r ? l : r);
}
 
// A Binary Tree Node  
public class Node
{
    public int data;
    public Node left, right;
}
 
public class INT
{
    public int v;
public INT(int a)
{
    v = a;
}
}
 
// A utility function to create  
// a new Binary Tree node with 
// given data  
public static Node newNode(int data)
{
    Node node = new Node();
    node.data = data;
    node.left = node.right = null;
    return node;
}
 
// print the tree in LVR  
// (Inorder traversal) way.  
public static void print(Node root)
{
    if (root != null)
    {
        print(root.left);
        Console.Write(root.data + " ");
        print(root.right);
    }
}
 
// Main function which 
// truncates the binary tree.  
public static Node pruneUtil(Node root, int k, INT sum)
{
    // Base Case  
    if (root == null)
    {
        return null;
    }
 
    // Initialize left and right  
    // sums as sum from root to  
    // this node (including this node)  
    INT lsum = new INT(sum.v + (root.data));
    INT rsum = new INT(lsum.v);
 
    // Recursively prune left  
    // and right subtrees  
    root.left = pruneUtil(root.left, k, lsum);
    root.right = pruneUtil(root.right, k, rsum);
 
    // Get the maximum of 
    // left and right sums  
    sum.v = max(lsum.v, rsum.v);
 
    // If maximum is smaller  
    // than k, then this node  
    // must be deleted  
    if (sum.v < k)
    {
 
        root = null;
    }
 
    return root;
}
 
// A wrapper over pruneUtil()  
public static Node prune(Node root, int k)
{
    INT sum = new INT(0);
    return pruneUtil(root, k, sum);
}
 
// Driver Code 
public static void Main(string[] args)
{
    int k = 45;
    Node root = newNode(1);
    root.left = newNode(2);
    root.right = newNode(3);
    root.left.left = newNode(4);
    root.left.right = newNode(5);
    root.right.left = newNode(6);
    root.right.right = newNode(7);
    root.left.left.left = newNode(8);
    root.left.left.right = newNode(9);
    root.left.right.left = newNode(12);
    root.right.right.left = newNode(10);
    root.right.right.left.right = newNode(11);
    root.left.left.right.left = newNode(13);
    root.left.left.right.right = newNode(14);
    root.left.left.right.right.left = newNode(15);
 
    Console.WriteLine("Tree before truncation\n");
    print(root);
 
    root = prune(root, k); // k is 45
 
    Console.WriteLine("\n\nTree after truncation\n");
    print(root);
}
}
 
  // This code is contributed by Shrikant13

Javascript

<script>
 
// Javascript program to implement
// the above approach
 
// A utility function to get
// maximum of two integers 
function max(l, r) 
{ 
    return (l > r ? l : r);
} 
 
class Node
{
    constructor(data)
    {
        this.left = null;
        this.right = null;
        this.data = data;
    }
}
 
class INT
{
    constructor(a) 
    {
        this.v = a;
    }
}
 
// A utility function to create 
// a new Binary Tree node with
// given data 
function newNode(data) 
{ 
    let node = new Node(data); 
    return node; 
} 
 
// print the tree in LVR 
// (Inorder traversal) way. 
function print(root) 
{ 
    if (root != null) 
    { 
        print(root.left); 
        document.write(root.data + " "); 
        print(root.right); 
    } 
} 
 
// Main function which
// truncates the binary tree. 
function pruneUtil(root, k, sum) 
{ 
     
    // Base Case 
    if (root == null) 
        return null; 
 
    // Initialize left and right 
    // sums as sum from root to 
    // this node (including this node) 
    let lsum = new INT(sum.v + (root.data)); 
    let rsum = new INT(lsum.v); 
 
    // Recursively prune left 
    // and right subtrees 
    root.left = pruneUtil(root.left, k, lsum); 
    root.right = pruneUtil(root.right, k, rsum); 
 
    // Get the maximum of
    // left and right sums 
    sum.v = max(lsum.v, rsum.v); 
 
    // If maximum is smaller 
    // than k, then this node 
    // must be deleted 
    if (sum.v < k) 
    { 
        root = null; 
    } 
    return root; 
} 
 
// A wrapper over pruneUtil() 
function prune(root, k) 
{ 
    let sum = new INT(0); 
    return pruneUtil(root, k, sum);
} 
 
// Driver code
let k = 45; 
let root = newNode(1); 
root.left = newNode(2); 
root.right = newNode(3); 
root.left.left = newNode(4); 
root.left.right = newNode(5); 
root.right.left = newNode(6); 
root.right.right = newNode(7); 
root.left.left.left = newNode(8); 
root.left.left.right = newNode(9); 
root.left.right.left = newNode(12); 
root.right.right.left = newNode(10); 
root.right.right.left.right = newNode(11); 
root.left.left.right.left = newNode(13); 
root.left.left.right.right = newNode(14); 
root.left.left.right.right.left = newNode(15); 
 
document.write("Tree before truncation" + "</br>"); 
print(root); 
 
root = prune(root, k); // k is 45 
 
document.write("</br></br>" + 
               "Tree after truncation" + "</br>"); 
print(root); 
 
// This code is contributed by decode2207
 
</script>

Output

Tree before truncation
 8 4 13 9 15 14 2 12 5 1 6 3 10 11 7

Tree after truncation
 4 9 15 14 2 1

Time Complexity: O(n)

The solution does a single traversal of given Binary Tree.

Auxiliary Space: O(h)

Here h is the height of the tree and the extra space is used due to recursion call stack.

A Simpler Solution:

The above code can be simplified using the fact that nodes are deleted in bottom up manner. The idea is to keep reducing the sum when traversing down. When we reach a leaf and sum is greater than the leaf’s data, then we delete the leaf. Note that deleting nodes may convert a non-leaf node to a leaf node and if the data for the converted leaf node is less than the current sum, then the converted leaf should also be deleted.
Thanks to vicky for suggesting this solution in below comments.

C++

#include <bits/stdc++.h>
using namespace std;
 
// A Binary Tree Node
struct Node
{
    int data;
    struct Node *left, *right;
};
 
// A utility function to create a new Binary
// Tree node with given data
struct Node* newNode(int data)
{
    struct Node* node =
    (struct Node*) malloc(sizeof(struct Node));
    node->data = data;
    node->left = node->right = NULL;
    return node;
}
 
// print the tree in LVR (Inorder traversal) way.
void print(struct Node *root)
{
    if (root != NULL)
    {
        print(root->left);
        cout << root->data << " ";
        print(root->right);
    }
}
 
/* Main function which truncates the binary tree. */
struct Node *prune(struct Node *root, int sum)
{
    // Base Case
    if (root == NULL) return NULL;
 
    // Recur for left and right subtrees
    root->left = prune(root->left, sum - root->data);
    root->right = prune(root->right, sum - root->data);
 
    // If we reach leaf whose data is smaller than sum,
    // we delete the leaf. An important thing to note
    // is a non-leaf node can become leaf when its
    // children are deleted.
    if (root->left==NULL && root->right==NULL)
    {
        if (root->data < sum)
        {
            free(root);
            return NULL;
        }
    }
 
    return root;
}
 
// Driver program to test above function
int main()
{
    int k = 45;
    struct Node *root = newNode(1);
    root->left = newNode(2);
    root->right = newNode(3);
    root->left->left = newNode(4);
    root->left->right = newNode(5);
    root->right->left = newNode(6);
    root->right->right = newNode(7);
    root->left->left->left = newNode(8);
    root->left->left->right = newNode(9);
    root->left->right->left = newNode(12);
    root->right->right->left = newNode(10);
    root->right->right->left->right = newNode(11);
    root->left->left->right->left = newNode(13);
    root->left->left->right->right = newNode(14);
    root->left->left->right->right->left = newNode(15);
 
    cout << "Tree before truncation\n";
    print(root);
 
    root = prune(root, k); // k is 45
 
    cout << "\n\nTree after truncation\n";
    print(root);
 
    return 0;
}
 
// This code is contributed
// by Akanksha Rai

C

#include <stdio.h>
#include <stdlib.h>
 
// A Binary Tree Node
struct Node
{
    int data;
    struct Node *left, *right;
};
 
// A utility function to create a new Binary
// Tree node with given data
struct Node* newNode(int data)
{
    struct Node* node =
       (struct Node*) malloc(sizeof(struct Node));
    node->data = data;
    node->left = node->right = NULL;
    return node;
}
 
// print the tree in LVR (Inorder traversal) way.
void print(struct Node *root)
{
    if (root != NULL)
    {
        print(root->left);
        printf("%d ",root->data);
        print(root->right);
    }
}
 
/* Main function which truncates the binary tree. */
struct Node *prune(struct Node *root, int sum)
{
    // Base Case
    if (root == NULL) return NULL;
 
    // Recur for left and right subtrees
    root->left = prune(root->left, sum - root->data);
    root->right = prune(root->right, sum - root->data);
 
    // If we reach leaf whose data is smaller than sum,
    // we delete the leaf.  An important thing to note
    // is a non-leaf node can become leaf when its
    // children are deleted.
    if (root->left==NULL && root->right==NULL)
    {
        if (root->data < sum)
        {
            free(root);
            return NULL;
        }
    }
 
    return root;
}
 
// Driver program to test above function
int main()
{
    int k = 45;
    struct Node *root = newNode(1);
    root->left = newNode(2);
    root->right = newNode(3);
    root->left->left = newNode(4);
    root->left->right = newNode(5);
    root->right->left = newNode(6);
    root->right->right = newNode(7);
    root->left->left->left = newNode(8);
    root->left->left->right = newNode(9);
    root->left->right->left = newNode(12);
    root->right->right->left = newNode(10);
    root->right->right->left->right = newNode(11);
    root->left->left->right->left = newNode(13);
    root->left->left->right->right = newNode(14);
    root->left->left->right->right->left = newNode(15);
 
    printf("Tree before truncation\n");
    print(root);
 
    root = prune(root, k); // k is 45
 
    printf("\n\nTree after truncation\n");
    print(root);
 
    return 0;
}

Java

// Java program to remove all nodes which donot 
// lie on path having sum>= k
 
// Class representing binary tree node
class Node {
    int data;
    Node left;
    Node right;
 
    // Constructor to create a new node
    public Node(int data) {
        this.data = data;
        left = null;
        right = null;
    }
}
 
// class to truncate binary tree
class BinaryTree {
    Node root;
 
    // recursive method to truncate binary tree
    public Node prune(Node root, int sum) {
 
        // base case
        if (root == null)
            return null;
 
        // recur for left and right subtree
        root.left = prune(root.left, sum - root.data);
        root.right = prune(root.right, sum - root.data);
 
        // if node is a leaf node whose data is smaller
        // than the sum we delete the leaf.An important
        // thing to note is a non-leaf node can become
        // leaf when its children are deleted.
        if (isLeaf(root)) {
            if (sum > root.data)
                root = null;
        }
 
        return root;
    } 
 
    // utility method to check if node is leaf
    public boolean isLeaf(Node root) {
        if (root == null)
            return false;
        if (root.left == null && root.right == null)
            return true;
        return false;
    }
 
    // for print traversal
    public void print(Node root) {
 
        // base case
        if (root == null)
            return;
 
        print(root.left);
        System.out.print(root.data + " ");
        print(root.right);
    }
}
 
// Driver class to test above function
public class GFG {
    public static void main(String args[]) {
 
        BinaryTree tree = new BinaryTree();
 
        tree.root = new Node(1);
        tree.root.left = new Node(2);
        tree.root.right = new Node(3);
        tree.root.left.left = new Node(4);
        tree.root.left.right = new Node(5);
        tree.root.right.left = new Node(6);
        tree.root.right.right = new Node(7);
        tree.root.left.left.left = new Node(8);
        tree.root.left.left.right = new Node(9);
        tree.root.left.right.left = new Node(12);
        tree.root.right.right.left = new Node(10);
        tree.root.right.right.left.right = new Node(11);
        tree.root.left.left.right.left = new Node(13);
        tree.root.left.left.right.right = new Node(14);
        tree.root.left.left.right.right.left = new Node(15);
 
        System.out.println("Tree before truncation");
        tree.print(tree.root);
 
        tree.prune(tree.root, 45);
 
        System.out.println("\nTree after truncation");
        tree.print(tree.root);
    }
}
 
// This code is contributed by Shweta Singh

Python3

"""
Python program to remove all nodes which don’t
lie in any path with sum>= k
"""
 
# binary tree node contains data field , left
# and right pointer
class Node:
     
    # constructor to create tree node
    def __init__(self, data):
        self.data = data
        self.left = None
        self.right = None
 
# Function to remove all nodes which do not
# lie in the sum path
def prune(root, sum):
 
    # Base case
    if root is None:
        return None
 
    # Recur for left and right subtree
    root.left = prune(root.left, sum - root.data)
    root.right = prune(root.right, sum - root.data)
 
    # if node is leaf and sum is found greater
    # than data than remove node An important 
    # thing to remember is that a non-leaf node 
    # can become a leaf when its children are 
    # removed
    if root.left is None and root.right is None:
        if sum > root.data:
            return None
 
    return root
 
# inorder traversal
def inorder(root):
    if root is None:
        return
    inorder(root.left)
    print(root.data, "", end="")
    inorder(root.right)
 
# Driver program to test above function
root = Node(1)
root.left = Node(2)
root.right = Node(3)
root.left.left = Node(4)
root.left.right = Node(5)
root.right.left = Node(6)
root.right.right = Node(7)
root.left.left.left = Node(8)
root.left.left.right = Node(9)
root.left.right.left = Node(12)
root.right.right.left = Node(10)
root.right.right.left.right = Node(11)
root.left.left.right.left = Node(13)
root.left.left.right.right = Node(14)
root.left.left.right.right.left = Node(15)
 
print("Tree before truncation")
inorder(root)
prune(root, 45)
print("\nTree after truncation")
inorder(root)
 
# This code is contributed by Shweta Singh

C#

using System;
 
// C# program to remove all nodes which donot  
// lie on path having sum>= k 
 
// Class representing binary tree node 
public class Node
{
    public int data;
    public Node left;
    public Node right;
 
    // Constructor to create a new node 
    public Node(int data)
    {
        this.data = data;
        left = null;
        right = null;
    }
}
 
// class to truncate binary tree 
public class BinaryTree
{
    public Node root;
 
    // recursive method to truncate binary tree 
    public virtual Node prune(Node root, int sum)
    {
 
        // base case 
        if (root == null)
        {
            return null;
        }
 
        // recur for left and right subtree 
        root.left = prune(root.left, sum - root.data);
        root.right = prune(root.right, sum - root.data);
 
        // if node is a leaf node whose data is smaller 
        // than the sum we delete the leaf.An important 
        // thing to note is a non-leaf node can become 
        // leaf when its children are deleted. 
        if (isLeaf(root))
        {
            if (sum > root.data)
            {
                root = null;
            }
        }
 
        return root;
    }
 
    // utility method to check if node is leaf 
    public virtual bool isLeaf(Node root)
    {
        if (root == null)
        {
            return false;
        }
        if (root.left == null && root.right == null)
        {
            return true;
        }
        return false;
    }
 
    // for print traversal 
    public virtual void print(Node root)
    {
 
        // base case 
        if (root == null)
        {
            return;
        }
 
        print(root.left);
        Console.Write(root.data + " ");
        print(root.right);
    }
}
 
// Driver class to test above function 
public class GFG
{
    public static void Main(string[] args)
    {
 
        BinaryTree tree = new BinaryTree();
 
        tree.root = new Node(1);
        tree.root.left = new Node(2);
        tree.root.right = new Node(3);
        tree.root.left.left = new Node(4);
        tree.root.left.right = new Node(5);
        tree.root.right.left = new Node(6);
        tree.root.right.right = new Node(7);
        tree.root.left.left.left = new Node(8);
        tree.root.left.left.right = new Node(9);
        tree.root.left.right.left = new Node(12);
        tree.root.right.right.left = new Node(10);
        tree.root.right.right.left.right = new Node(11);
        tree.root.left.left.right.left = new Node(13);
        tree.root.left.left.right.right = new Node(14);
        tree.root.left.left.right.right.left = new Node(15);
 
        Console.WriteLine("Tree before truncation");
        tree.print(tree.root);
 
        tree.prune(tree.root, 45);
 
        Console.WriteLine("\nTree after truncation");
        tree.print(tree.root);
    }
}
 
  // This code is contributed by Shrikant13

Javascript

<script>
 
      // JavaScript program to remove all nodes which donot
      // lie on path having sum>= k
 
      // Class representing binary tree node
      class Node {
        // Constructor to create a new node
        constructor(data) {
          this.data = data;
          this.left = null;
          this.right = null;
        }
      }
 
      // class to truncate binary tree
      class BinaryTree {
        constructor() {
          this.root = null;
        }
 
        // recursive method to truncate binary tree
        prune(root, sum) {
          // base case
          if (root == null) {
            return null;
          }
 
          // recur for left and right subtree
          root.left = this.prune(root.left, sum - root.data);
          root.right = this.prune(root.right, sum - root.data);
 
          // if node is a leaf node whose data is smaller
          // than the sum we delete the leaf.An important
          // thing to note is a non-leaf node can become
          // leaf when its children are deleted.
          if (this.isLeaf(root)) {
            if (sum > root.data) {
              root = null;
            }
          }
 
          return root;
        }
 
        // utility method to check if node is leaf
        isLeaf(root) {
          if (root == null) {
            return false;
          }
          if (root.left == null && root.right == null) {
            return true;
          }
          return false;
        }
 
        // for print traversal
        print(root) {
          // base case
          if (root == null) {
            return;
          }
 
          this.print(root.left);
          document.write(root.data + " ");
          this.print(root.right);
        }
      }
 
      // Driver class to test above function
      var tree = new BinaryTree();
 
      tree.root = new Node(1);
      tree.root.left = new Node(2);
      tree.root.right = new Node(3);
      tree.root.left.left = new Node(4);
      tree.root.left.right = new Node(5);
      tree.root.right.left = new Node(6);
      tree.root.right.right = new Node(7);
      tree.root.left.left.left = new Node(8);
      tree.root.left.left.right = new Node(9);
      tree.root.left.right.left = new Node(12);
      tree.root.right.right.left = new Node(10);
      tree.root.right.right.left.right = new Node(11);
      tree.root.left.left.right.left = new Node(13);
      tree.root.left.left.right.right = new Node(14);
      tree.root.left.left.right.right.left = new Node(15);
 
      document.write("Tree before truncation <br>");
      tree.print(tree.root);
 
      tree.prune(tree.root, 45);
 
      document.write("<br><br>Tree after truncation<br>");
      tree.print(tree.root);
       
</script>

Output

Tree before truncation
8 4 13 9 15 14 2 12 5 1 6 3 10 11 7 

Tree after truncation
4 9 15 14 2 1

Time Complexity: O(n)

As we are visiting every node only once.

Auxiliary Space: O(h)

Here h is the height of the tree and the extra space is used due to recursion call stack.

GeeksforGeeks

Improve

Previous Article

Check if there is a root to leaf path with given sequence

Maximum spiral sum in Binary Tree

Similar Reads

Construct a Tree whose sum of nodes of all the root to leaf path is not divisible by the count of nodes in that path

Given an N-ary tree consisting of N nodes numbered from 1 to N rooted at node 1, the task is to assign values to each node of the tree such that the sum of values from any root to the leaf path which contains at least two nodes is not divisible by the number of nodes along that path. Examples: Input: N = 11, edges[][] = {{1, 2}, {1, 3}, {1, 4}, {1,

Sum of array elements excluding the elements which lie between a and b

Given an array of N unique numbers. Also given two numbers a and b such that a will always be before b in the array. The task is to find the sum of the array elements excluding the elements which lie between a and b. Examples: Input : arr = [2, 1, 6, 9, 11], a = 6, b = 9 Output : 14 Input : arr = [1, 2, 4, 5, 6], a = 2, b = 5 Output : 7 Approach: T

Minimum edges to be removed from given undirected graph to remove any existing path between nodes A and B

Given two integers N and M denoting the number of vertices and edges in the graph and array edges[][] of size M, denoting an edge between edges[i][0] and edges[i][1], the task is to find the minimum edges directly connected with node B that must be removed such that there exist no path between vertex A and B. Examples: Input: N = 4, A = 3, B = 2, e

Print all nodes that don't have sibling

Given a Binary Tree, print all nodes that don't have a sibling (a sibling is a node that has same parent. In a Binary Tree, there can be at most one sibling). Root should not be printed as root cannot have a sibling.For example, the output should be "4 5 6" for the following tree. Recommended PracticePrint all nodes that don't have siblingTry It! T

Sum of all odd nodes in the path connecting two given nodes

Given a binary tree and two nodes of that binary tree. Find the sum of all nodes with odd values in the path connecting the two given nodes. For Example: In the above binary tree, sum of all odd nodes in the path between the nodes [Tex]5 [/Tex]and [Tex]6 [/Tex]will be 5 + 1 + 3 = 9. Source : Amazon Interview Experience on Campus Approach : The idea

Count BST nodes that lie in a given range

Given the head of a Binary Search Tree (BST) and a range (l, h), count the number of nodes that lie in the given range (l, h). Examples: Input: Range: [5, 45] 10 / \ 5 50 / / \ 1 40 100Output: 3Explanation: There are three nodes in range, 5, 10 and 40 Input: Range: [10, 100] 10 / \ 5 50 / / \ 1 40 100Output: 4 Recommended PracticeCount BST nodes th

Count of subarrays whose products don't have any repeating prime factor

Given an array of integers. Find the total number of subarrays whose product of all elements doesn't contain repeating prime factor in prime decomposition of resulting number. Examples: Input: 2 3 9 Output: 3 Explanation: Total sub-array are:- {2}, {3}, {9}, {2, 3}, {3, 9}, {2, 3, 9} Subarray which violets the property are:- {9} -> {3 * 3}, Sinc

Maximum path sum that starting with any cell of 0-th row and ending with any cell of (N-1)-th row

Given a N X N matrix Mat[N][N] of positive integers. There are only three possible moves from a cell (i, j) (i+1, j)(i+1, j-1)(i+1, j+1)Starting from any column in row 0, return the largest sum of any of the paths up to row N-1. Examples: Input : mat[4][4] = { {4, 2, 3, 4}, {2, 9, 1, 10}, {15, 1, 3, 0}, {16, 92, 41, 44} };Output :120path : 4 + 9 +

Count nodes with sum of path made by only left child nodes at least K

Given a binary tree and an integer K, the task is to write a program to count the number of nodes such that the path from the current node to a leaf consisting of only the left child of nodes has a sum greater than or equal to K. Examples: Input: K = 15, Tree: 8 / \ 9 10 / \ / \ 11 12 13 7 / \ / / / \ 6 9 6 7 15 11 Output: 4Explanation: Nodes with

Find a set of at most N/2 nodes from a Graph such that all remaining nodes are directly connected to one of the chosen nodes

Given an integer N, representing the number of nodes present in an undirected graph, with each node valued from 1 to N, and a 2D array Edges[][], representing the pair of vertices connected by an edge, the task is to find a set of at most N/2 nodes such that nodes that are not present in the set, are connected adjacent to any one of the nodes prese

Article Tags :

DSA
Tree

Practice Tags :

Tree