# Delete leaf nodes with value as x

Given a binary tree and a target integer x, delete all the leaf nodes having value as x. Also, delete the newly formed leaves with the target value as x.

Example:

```Input : x = 5
6
/
5       4
/
1     2       5
Output :
6
/
5       4
/
1     2
Inorder Traversal is 1 5 2 6 4
```

Source: Microsoft Interview

We traverse the tree in postorder fashion and recursively delete the nodes. The approach is very similar to this and this problem.

## C++

 `// CPP code to delete all leaves with given ` `// value. ` `#include ` `using` `namespace` `std; ` ` `  `// A binary tree node ` `struct` `Node { ` `    ``int` `data; ` `    ``struct` `Node *left, *right; ` `}; ` ` `  `// A utility function to allocate a new node ` `struct` `Node* newNode(``int` `data) ` `{ ` `    ``struct` `Node* newNode = ``new` `Node; ` `    ``newNode->data = data; ` `    ``newNode->left = newNode->right = NULL; ` `    ``return` `(newNode); ` `} ` ` `  `Node* deleteLeaves(Node* root, ``int` `x) ` `{ ` `    ``if` `(root == NULL) ` `        ``return` `NULL; ` `    ``root->left = deleteLeaves(root->left, x); ` `    ``root->right = deleteLeaves(root->right, x); ` ` `  `    ``if` `(root->data == x && root->left == NULL &&  ` `                          ``root->right == NULL) { ` `        ``delete``(root); ` `        ``return` `NULL; ` `    ``} ` `    ``return` `root; ` `} ` ` `  `void` `inorder(Node* root) ` `{ ` `    ``if` `(root == NULL) ` `        ``return``; ` `    ``inorder(root->left); ` `    ``cout << root->data << ``" "``; ` `    ``inorder(root->right); ` `} ` ` `  `// Driver program ` `int` `main(``void``) ` `{ ` `    ``struct` `Node* root = newNode(10); ` `    ``root->left = newNode(3); ` `    ``root->right = newNode(10); ` `    ``root->left->left = newNode(3); ` `    ``root->left->right = newNode(1); ` `    ``root->right->right = newNode(3); ` `    ``root->right->right->left = newNode(3); ` `    ``root->right->right->right = newNode(3); ` `    ``deleteLeaves(root, 3); ` `    ``cout << ``"Inorder traversal after deletion : "``; ` `    ``inorder(root); ` `    ``return` `0; ` `} `

## Java

 `// Java code to delete all leaves with given  ` `// value.  ` `class` `GfG {  ` ` `  `// A binary tree node  ` `static` `class` `Node {  ` `    ``int` `data;  ` `    ``Node left, right;  ` `} ` ` `  `// A utility function to allocate a new node  ` `static` `Node newNode(``int` `data)  ` `{  ` `    ``Node newNode = ``new` `Node();  ` `    ``newNode.data = data;  ` `    ``newNode.left = ``null``; ` `    ``newNode.right = ``null``;  ` `    ``return` `(newNode);  ` `}  ` ` `  `static` `Node deleteLeaves(Node root, ``int` `x)  ` `{  ` `    ``if` `(root == ``null``)  ` `        ``return` `null``;  ` `    ``root.left = deleteLeaves(root.left, x);  ` `    ``root.right = deleteLeaves(root.right, x);  ` ` `  `    ``if` `(root.data == x && root.left == ``null` `&& root.right == ``null``) {  ` ` `  `        ``return` `null``;  ` `    ``}  ` `    ``return` `root;  ` `}  ` ` `  `static` `void` `inorder(Node root)  ` `{  ` `    ``if` `(root == ``null``)  ` `        ``return``;  ` `    ``inorder(root.left);  ` `    ``System.out.print(root.data + ``" "``);  ` `    ``inorder(root.right);  ` `}  ` ` `  `// Driver program  ` `public` `static` `void` `main(String[] args)  ` `{  ` `    ``Node root = newNode(``10``);  ` `    ``root.left = newNode(``3``);  ` `    ``root.right = newNode(``10``);  ` `    ``root.left.left = newNode(``3``);  ` `    ``root.left.right = newNode(``1``);  ` `    ``root.right.right = newNode(``3``);  ` `    ``root.right.right.left = newNode(``3``);  ` `    ``root.right.right.right = newNode(``3``);  ` `    ``deleteLeaves(root, ``3``);  ` `    ``System.out.print(``"Inorder traversal after deletion : "``);  ` `    ``inorder(root);  ` `} ` `}  `

## Python3

# Python3 code to delete all leaves
# with given value.

# A utility class to allocate a new node
class newNode:
def __init__(self, data):
self.data = data
self.left = self.right = None

def deleteLeaves(root, x):
if (root == None):
return None
root.left = deleteLeaves(root.left, x)
root.right = deleteLeaves(root.right, x)

if (root.data == x and
root.left == None and
root.right == None):
return None
return root

def inorder(root):
if (root == None):
return
inorder(root.left)
print(root.data, end = ” “)
inorder(root.right)

# Driver Code
if __name__ == ‘__main__’:
root = newNode(10)
root.left = newNode(3)
root.right = newNode(10)
root.left.left = newNode(3)
root.left.right = newNode(1)
root.right.right = newNode(3)
root.right.right.left = newNode(3)
root.right.right.right = newNode(3)
deleteLeaves(root, 3)
print(“Inorder traversal after deletion : “)
inorder(root)

# This code is contributed by PranchalK

## C#

 `// C# code to delete all leaves with given  ` `// value. ` `using` `System; ` `     `  `class` `GfG  ` `{  ` ` `  `    ``// A binary tree node  ` `    ``class` `Node  ` `    ``{  ` `        ``public` `int` `data;  ` `        ``public` `Node left, right;  ` `    ``} ` ` `  `    ``// A utility function to allocate a new node  ` `    ``static` `Node newNode(``int` `data)  ` `    ``{  ` `        ``Node newNode = ``new` `Node();  ` `        ``newNode.data = data;  ` `        ``newNode.left = ``null``; ` `        ``newNode.right = ``null``;  ` `        ``return` `(newNode);  ` `    ``}  ` ` `  `    ``static` `Node deleteLeaves(Node root, ``int` `x)  ` `    ``{  ` `        ``if` `(root == ``null``)  ` `            ``return` `null``;  ` `        ``root.left = deleteLeaves(root.left, x);  ` `        ``root.right = deleteLeaves(root.right, x);  ` ` `  `        ``if` `(root.data == x &&  ` `            ``root.left == ``null` `&&  ` `            ``root.right == ``null``)  ` `        ``{  ` ` `  `            ``return` `null``;  ` `        ``}  ` `        ``return` `root;  ` `    ``}  ` ` `  `    ``static` `void` `inorder(Node root)  ` `    ``{  ` `        ``if` `(root == ``null``)  ` `            ``return``;  ` `        ``inorder(root.left);  ` `        ``Console.Write(root.data + ``" "``);  ` `        ``inorder(root.right);  ` `    ``}  ` ` `  `    ``// Driver code  ` `    ``public` `static` `void` `Main(String[] args)  ` `    ``{  ` `        ``Node root = newNode(10);  ` `        ``root.left = newNode(3);  ` `        ``root.right = newNode(10);  ` `        ``root.left.left = newNode(3);  ` `        ``root.left.right = newNode(1);  ` `        ``root.right.right = newNode(3);  ` `        ``root.right.right.left = newNode(3);  ` `        ``root.right.right.right = newNode(3);  ` `        ``deleteLeaves(root, 3);  ` `        ``Console.Write(``"Inorder traversal after deletion : "``);  ` `        ``inorder(root);  ` `    ``} ` `} ` ` `  `// This code is contributed by PrinciRaj1992 `

Output:

```Inorder traversal after deletion : 3 1 10 10
```

## tags:

Tree tree-traversal Tree

code