Skip to main content

Delete leaf node with given value

In computer science and programming, a binary tree is a type of data structure that consists of nodes, each of which has at most two children, referred to as the left child and the right child. A leaf node is a node in a binary tree that has no children.

Deleting a leaf node with a given value means removing a node with the specified value from the binary tree, but only if it is a leaf node. If the node has any children, it cannot be deleted.

To delete a leaf node with a given value from a binary tree, the following steps can be taken:

  1. Traverse the binary tree to find the node with the given value.
  2. Check if the node is a leaf node, i.e., it has no children.
  3. If the node is a leaf node, delete it from the tree.
  4. If the node is not a leaf node, do nothing.

Note that deleting a leaf node may also require updating the parent node's reference to the deleted node to null or updating it to point to a different node.

Program List

/*
  C Program  
  Delete leaf node with given value
*/
#include <stdio.h>

#include <stdlib.h>

//Binary Tree node
struct Node
{
	int data;
	struct Node *left, *right;
};
//This is creating a binary tree node and return this
struct Node *add_node(int data)
{
	// Create dynamic node
	struct Node *new_node = (struct Node *) malloc(sizeof(struct Node));
	if (new_node != NULL)
	{
		//Set data and pointer values
		new_node->data = data;
		new_node->left = NULL;
		new_node->right = NULL;
	}
	else
	{
		//This is indicates, segmentation fault or memory overflow problem
		printf("Memory Overflow\n");
	}
	//return new node
	return new_node;
}
//Recursive function
//Display preorder view of binary tree
void pre_order(struct Node *node)
{
	if (node != NULL)
	{
		//Print node value
		printf("  %d", node->data);
		pre_order(node->left);
		pre_order(node->right);
	}
}
//Recursively process, deleting leaf nodes which equal to given key
struct Node *delete_leaf_key(struct Node *node, int key, int *status)
{
	if (node != NULL)
	{
		//Recursive execute, left and right subtree
		node->left = delete_leaf_key(node->left, key, status);
		node->right = delete_leaf_key(node->right, key, status);
		if (node->left == NULL && node->right == NULL && node->data == key)
		{
			//When get a deleted leaf node
			*status = 1;
			free(node);
			node = NULL;
			//This is deleted leaf node
			return NULL;
		}
		return node;
	}
	else
	{
		return NULL;
	}
}
//This is used to handle the request of delete leaf nodes by given key
struct Node *delete_node(struct Node *root, int key)
{
	if (root == NULL)
	{
		printf("\nEmpty Tree\n");
		return NULL;
	}
	else
	{
		// Before delete, display tree elements
		printf("\n  Before delete leaf key %d is ", key);
		printf("\n  Tree Element \n");
		pre_order(root);
		// Use to detect
		int status = 0;
		// Delete leaf nodes
		root = delete_leaf_key(root, key, &status);
		if (status == 1)
		{
			//When delete key is exist in leaves position
			printf("\n  After delete leaf key %d is ", key);
			printf("\n  Tree Element \n");
			pre_order(root);
			printf("\n");
		}
		else
		{
			// When deleted node not exist in leaves position 
			printf("\n  Leaf key %d not exist\n", key);
		}
		return root;
	}
}
int main()
{
	struct Node *root = NULL;
	/*
	Construct Binary Tree
	-----------------------
	      10
	     /   \
	    6     8
	   / \   / \
	  2   3 7   2
	 /       \   \
	9        -1   9
	*/
	//Add nodes
	root = add_node(10);
	root->left = add_node(6);
	root->left->left = add_node(2);
	root->right = add_node(8);
	root->right->right = add_node(2);
	root->right->left = add_node(7);
	root->left->left->left = add_node(9);
	root->right->left->right = add_node(-1);
	root->left->right = add_node(3);
	root->right->right->right = add_node(9);
	//Test execution
	root = delete_node(root, 9);
	root = delete_node(root, 2);
	root = delete_node(root, -1);
	return 0;
}

Output

  Before delete leaf key 9 is
  Tree Element
  10  6  2  9  3  8  7  -1  2  9
  After delete leaf key 9 is
  Tree Element
  10  6  2  3  8  7  -1  2

  Before delete leaf key 2 is
  Tree Element
  10  6  2  3  8  7  -1  2
  After delete leaf key 2 is
  Tree Element
  10  6  3  8  7  -1

  Before delete leaf key -1 is
  Tree Element
  10  6  3  8  7  -1
  After delete leaf key -1 is
  Tree Element
  10  6  3  8  7
// Java Program 
// Delete leaf node with given value

//Binary Tree node
class Node
{
	public int data;
	public Node left;
	public Node right;
	public Node(int data)
	{
		//set node value
		this.data = data;
		this.left = null;
		this.right = null;
	}
}
class BinaryTree
{
	public Node root;
	//indicator
	public static boolean status = false;
	public BinaryTree()
	{
		//set initial tree root to null
		this.root = null;
	}
	//Recursive function
	//Display preorder view of binary tree
	public void pre_order(Node node)
	{
		if (node != null)
		{
			//Print node value
			System.out.print(" " + node.data);
			pre_order(node.left);
			pre_order(node.right);
		}
	}
	//Recursively process, deleting leaf nodes which equal to given key
	public Node delete_leaf_key(Node node, int key)
	{
		if (node != null)
		{
			//Recursive execute, left and right subtree
			node.left = delete_leaf_key(node.left, key);
			node.right = delete_leaf_key(node.right, key);
			if (node.left == null && node.right == null && node.data == key)
			{
				//When get a deleted leaf node
				status = true;
				//This is deleted leaf node
				return null;
			}
			return node;
		}
		else
		{
			return null;
		}
	}
	//This is used to handle the request of delete leaf nodes by given key
	public Node delete_node(int key)
	{
		if (this.root == null)
		{
			System.out.print("\nEmpty Tree\n");
			return null;
		}
		else
		{
			// Before delete, display tree elements
			System.out.print("\n Before delete leaf key " + key + " is ");
			System.out.print("\n Tree Element \n");
			pre_order(this.root);
			status = false;
			// Deleting leaf by given key  
			this.root = delete_leaf_key(this.root, key);
			if (status == true)
			{
				//When delete key is exist in leaves position
				System.out.print("\n After delete leaf key " + key + " is ");
				System.out.print("\n Tree Element \n");
				pre_order(root);
				System.out.print("\n");
			}
			else
			{
				// When deleted node not exist in leaves position 
				System.out.print("\n Leaf key " + key + " not exist\n");
			}
			return root;
		}
	}
	public static void main(String[] args)
	{
		//Make object 
		BinaryTree obj = new BinaryTree();
		/*
		    Construct Binary Tree
		    -----------------------
		          10
		         /   \
		        6     8
		       / \   / \
		      2   3 7   2
		     /       \   \
		    9        -1   9
		*/
		//Add nodes
		obj.root = new Node(10);
		obj.root.left = new Node(6);
		obj.root.left.left = new Node(2);
		obj.root.right = new Node(8);
		obj.root.right.right = new Node(2);
		obj.root.right.left = new Node(7);
		obj.root.left.left.left = new Node(9);
		obj.root.right.left.right = new Node(-1);
		obj.root.left.right = new Node(3);
		obj.root.right.right.right = new Node(9);
		//Test execution
		obj.root = obj.delete_node(9);
		obj.root = obj.delete_node(2);
		obj.root = obj.delete_node(-1);
	}
}

Output

 Before delete leaf key 9 is
 Tree Element
 10 6 2 9 3 8 7 -1 2 9
 After delete leaf key 9 is
 Tree Element
 10 6 2 3 8 7 -1 2

 Before delete leaf key 2 is
 Tree Element
 10 6 2 3 8 7 -1 2
 After delete leaf key 2 is
 Tree Element
 10 6 3 8 7 -1

 Before delete leaf key -1 is
 Tree Element
 10 6 3 8 7 -1
 After delete leaf key -1 is
 Tree Element
 10 6 3 8 7
//Include header file
#include <iostream>

using namespace std;
// C++ Program 
// Delete leaf node with given value
//Binary Tree node
class Node
{
	public: 
    int data;
	Node *left;
	Node *right;
	Node(int data)
	{
		//set node value
		this->data = data;
		this->left = NULL;
		this->right = NULL;
	}
};
class BinaryTree
{
	public: 
    Node *root;
	
	BinaryTree()
	{
		//set initial tree root to null
		this->root = NULL;
	}
	//Recursive function
	//Display preorder view of binary tree
	void pre_order(Node *node)
	{
		if (node != NULL)
		{
			//Print node value
			cout << " " << node->data;
			this->pre_order(node->left);
			this->pre_order(node->right);
		}
	}
	//Recursively process, deleting leaf nodes which equal to given key
	Node *delete_leaf_key(Node *node, int key,bool *status)
	{
		if (node != NULL)
		{
			//Recursive execute, left and right subtree
			node->left = this->delete_leaf_key(node->left, key,status);
			node->right = this->delete_leaf_key(node->right, key,status);
			if (node->left == NULL && node->right == NULL && node->data == key)
			{
				//When get a deleted leaf node
				*status = true;
				//This is deleted leaf node
				return NULL;
			}
			return node;
		}
		else
		{
			return NULL;
		}
	}
	//This is used to handle the request of delete leaf nodes by given key
	Node *delete_node(int key)
	{
		if (this->root == NULL)
		{
			cout << "\nEmpty Tree\n";
			return NULL;
		}
		else
		{
			// Before delete, display tree elements
			cout << "\n Before delete leaf key " << key << " is ";
			cout << "\n Tree Element \n";
			this->pre_order(this->root);
			bool status = false;
			// Deleting leaf by given key  
			this->root = this->delete_leaf_key(this->root, key,&status);
			if (status == true)
			{
				//When delete key is exist in leaves position
				cout << "\n After delete leaf key " << key << " is ";
				cout << "\n Tree Element \n";
				this->pre_order(this->root);
				cout << "\n";
			}
			else
			{
				// When deleted node not exist in leaves position 
				cout << "\n Leaf key " << key << " not exist\n";
			}
			return this->root;
		}
	}
};
int main()
{
	//Make object 
	BinaryTree obj = BinaryTree();
	/*
			    Construct Binary Tree
			    -----------------------
			          10
			         /   \
			        6     8
			       / \   / \
			      2   3 7   2
			     /       \   \
			    9        -1   9
			*/
	//Add nodes
	obj.root = new Node(10);
	obj.root->left = new Node(6);
	obj.root->left->left = new Node(2);
	obj.root->right = new Node(8);
	obj.root->right->right = new Node(2);
	obj.root->right->left = new Node(7);
	obj.root->left->left->left = new Node(9);
	obj.root->right->left->right = new Node(-1);
	obj.root->left->right = new Node(3);
	obj.root->right->right->right = new Node(9);
	//Test execution
	obj.root = obj.delete_node(9);
	obj.root = obj.delete_node(2);
	obj.root = obj.delete_node(-1);
	return 0;
}

Output

 Before delete leaf key 9 is
 Tree Element
 10 6 2 9 3 8 7 -1 2 9
 After delete leaf key 9 is
 Tree Element
 10 6 2 3 8 7 -1 2

 Before delete leaf key 2 is
 Tree Element
 10 6 2 3 8 7 -1 2
 After delete leaf key 2 is
 Tree Element
 10 6 3 8 7 -1

 Before delete leaf key -1 is
 Tree Element
 10 6 3 8 7 -1
 After delete leaf key -1 is
 Tree Element
 10 6 3 8 7
//Include namespace system
using System;

// C# Program 
// Delete leaf node with given value

//Binary Tree node
class Node
{
	public int data;
	public Node left;
	public Node right;
	public Node(int data)
	{
		//set node value
		this.data = data;
		this.left = null;
		this.right = null;
	}
}
class BinaryTree
{
	public Node root;
	//indicator
	public static Boolean status = false;
	public BinaryTree()
	{
		//set initial tree root to null
		this.root = null;
	}
	//Recursive function
	//Display preorder view of binary tree
	public void pre_order(Node node)
	{
		if (node != null)
		{
			//Print node value
			Console.Write(" " + node.data);
			pre_order(node.left);
			pre_order(node.right);
		}
	}
	//Recursively process, deleting leaf nodes which equal to given key
	public Node delete_leaf_key(Node node, int key)
	{
		if (node != null)
		{
			//Recursive execute, left and right subtree
			node.left = delete_leaf_key(node.left, key);
			node.right = delete_leaf_key(node.right, key);
			if (node.left == null && node.right == null && node.data == key)
			{
				//When get a deleted leaf node
				status = true;
				//This is deleted leaf node
				return null;
			}
			return node;
		}
		else
		{
			return null;
		}
	}
	//This is used to handle the request of delete leaf nodes by given key
	public Node delete_node(int key)
	{
		if (this.root == null)
		{
			Console.Write("\nEmpty Tree\n");
			return null;
		}
		else
		{
			// Before delete, display tree elements
			Console.Write("\n Before delete leaf key " + key + " is ");
			Console.Write("\n Tree Element \n");
			pre_order(this.root);
			status = false;
			// Deleting leaf by given key  
			this.root = delete_leaf_key(this.root, key);
			if (status == true)
			{
				//When delete key is exist in leaves position
				Console.Write("\n After delete leaf key " + key + " is ");
				Console.Write("\n Tree Element \n");
				pre_order(root);
				Console.Write("\n");
			}
			else
			{
				// When deleted node not exist in leaves position 
				Console.Write("\n Leaf key " + key + " not exist\n");
			}
			return root;
		}
	}
	public static void Main(String[] args)
	{
		//Make object 
		BinaryTree obj = new BinaryTree();
		/*
				    Construct Binary Tree
				    -----------------------
				          10
				         /   \
				        6     8
				       / \   / \
				      2   3 7   2
				     /       \   \
				    9        -1   9
				*/
		//Add nodes
		obj.root = new Node(10);
		obj.root.left = new Node(6);
		obj.root.left.left = new Node(2);
		obj.root.right = new Node(8);
		obj.root.right.right = new Node(2);
		obj.root.right.left = new Node(7);
		obj.root.left.left.left = new Node(9);
		obj.root.right.left.right = new Node(-1);
		obj.root.left.right = new Node(3);
		obj.root.right.right.right = new Node(9);
		//Test execution
		obj.root = obj.delete_node(9);
		obj.root = obj.delete_node(2);
		obj.root = obj.delete_node(-1);
	}
}

Output

 Before delete leaf key 9 is
 Tree Element
 10 6 2 9 3 8 7 -1 2 9
 After delete leaf key 9 is
 Tree Element
 10 6 2 3 8 7 -1 2

 Before delete leaf key 2 is
 Tree Element
 10 6 2 3 8 7 -1 2
 After delete leaf key 2 is
 Tree Element
 10 6 3 8 7 -1

 Before delete leaf key -1 is
 Tree Element
 10 6 3 8 7 -1
 After delete leaf key -1 is
 Tree Element
 10 6 3 8 7
<?php
// Php Program 
// Delete leaf node with given value

//Binary Tree node
class Node
{
	public $data;
	public $left;
	public $right;

	function __construct($data)
	{
		//set node value
		$this->data = $data;
		$this->left = null;
		$this->right = null;
	}
}
class BinaryTree
{
	public $root;
	//indicator
	public static $status = false;

	function __construct()
	{
		//set initial tree root to null
		$this->root = null;
	}
	//Recursive function
	//Display preorder view of binary tree
	public	function pre_order($node)
	{
		if ($node != null)
		{
			//Print node value
			echo " ". $node->data;
			$this->pre_order($node->left);
			$this->pre_order($node->right);
		}
	}
	//Recursively process, deleting leaf nodes which equal to given key
	public	function delete_leaf_key($node, $key)
	{
		if ($node != null)
		{
			//Recursive execute, left and right subtree
			$node->left = $this->delete_leaf_key($node->left, $key);
			$node->right = $this->delete_leaf_key($node->right, $key);
			if ($node->left == null && $node->right == null && $node->data == $key)
			{
				//When get a deleted leaf node
				self::$status = true;
				//This is deleted leaf node
				return null;
			}
			return $node;
		}
		else
		{
			return null;
		}
	}
	//This is used to handle the request of delete leaf nodes by given key
	public	function delete_node($key)
	{
		if ($this->root == null)
		{
			echo "\nEmpty Tree\n";
			return null;
		}
		else
		{
			// Before delete, display tree elements
			echo "\n Before delete leaf key ". $key ." is ";
			echo "\n Tree Element \n";
			$this->pre_order($this->root);
			self::$status = false;
			// Deleting leaf by given key  
			$this->root = $this->delete_leaf_key($this->root, $key);
			if (self::$status == true)
			{
				//When delete key is exist in leaves position
				echo "\n After delete leaf key ". $key ." is ";
				echo "\n Tree Element \n";
				$this->pre_order($this->root);
				echo "\n";
			}
			else
			{
				// When deleted node not exist in leaves position 
				echo "\n Leaf key ". $key ." not exist\n";
			}
			return $this->root;
		}
	}
}

function main()
{
	//Make object 
	$obj = new BinaryTree();
	/*
			    Construct Binary Tree
			    -----------------------
			          10
			         /   \
			        6     8
			       / \   / \
			      2   3 7   2
			     /       \   \
			    9        -1   9
			*/
	//Add nodes
	$obj->root = new Node(10);
	$obj->root->left = new Node(6);
	$obj->root->left->left = new Node(2);
	$obj->root->right = new Node(8);
	$obj->root->right->right = new Node(2);
	$obj->root->right->left = new Node(7);
	$obj->root->left->left->left = new Node(9);
	$obj->root->right->left->right = new Node(-1);
	$obj->root->left->right = new Node(3);
	$obj->root->right->right->right = new Node(9);
	//Test execution
	$obj->root = $obj->delete_node(9);
	$obj->root = $obj->delete_node(2);
	$obj->root = $obj->delete_node(-1);
}
main();

Output

 Before delete leaf key 9 is
 Tree Element
 10 6 2 9 3 8 7 -1 2 9
 After delete leaf key 9 is
 Tree Element
 10 6 2 3 8 7 -1 2

 Before delete leaf key 2 is
 Tree Element
 10 6 2 3 8 7 -1 2
 After delete leaf key 2 is
 Tree Element
 10 6 3 8 7 -1

 Before delete leaf key -1 is
 Tree Element
 10 6 3 8 7 -1
 After delete leaf key -1 is
 Tree Element
 10 6 3 8 7
// Node Js Program 
// Delete leaf node with given value
//Binary Tree node
class Node
{
	constructor(data)
	{
		//set node value
		this.data = data;
		this.left = null;
		this.right = null;
	}
}
class BinaryTree
{

	constructor()
	{
		//set initial tree root to null
		this.root = null;
      //indicator
		BinaryTree.status = false;
	}
	//Recursive function
	//Display preorder view of binary tree
	pre_order(node)
	{
		if (node != null)
		{
			//Print node value
			process.stdout.write(" " + node.data);
			this.pre_order(node.left);
			this.pre_order(node.right);
		}
	}
	//Recursively process, deleting leaf nodes which equal to given key
	delete_leaf_key(node, key)
	{
		if (node != null)
		{
			//Recursive execute, left and right subtree
			node.left = this.delete_leaf_key(node.left, key);
			node.right = this.delete_leaf_key(node.right, key);
			if (node.left == null && node.right == null && node.data == key)
			{
				//When get a deleted leaf node
				this.status = true;
				//This is deleted leaf node
				return null;
			}
			return node;
		}
		else
		{
			return null;
		}
	}
	//This is used to handle the request of delete leaf nodes by given key
	delete_node(key)
	{
		if (this.root == null)
		{
			process.stdout.write("\nEmpty Tree\n");
			return null;
		}
		else
		{
			// Before delete, display tree elements
			process.stdout.write("\n Before delete leaf key " + key + " is ");
			process.stdout.write("\n Tree Element \n");
			this.pre_order(this.root);
			
			// Deleting leaf by given key  
			this.root = this.delete_leaf_key(this.root, key);
			if (this.status == true)
			{
				//When delete key is exist in leaves position
				process.stdout.write("\n After delete leaf key " + key + " is ");
				process.stdout.write("\n Tree Element \n");
				this.pre_order(this.root);
				process.stdout.write("\n");
			}
			else
			{
				// When deleted node not exist in leaves position 
				process.stdout.write("\n Leaf key " + key + " not exist\n");
			}
			return this.root;
		}
	}
}

function main()
{
	//Make object 
	var obj = new BinaryTree();
	/*
			    Construct Binary Tree
			    -----------------------
			          10
			         /   \
			        6     8
			       / \   / \
			      2   3 7   2
			     /       \   \
			    9        -1   9
			*/
	//Add nodes
	obj.root = new Node(10);
	obj.root.left = new Node(6);
	obj.root.left.left = new Node(2);
	obj.root.right = new Node(8);
	obj.root.right.right = new Node(2);
	obj.root.right.left = new Node(7);
	obj.root.left.left.left = new Node(9);
	obj.root.right.left.right = new Node(-1);
	obj.root.left.right = new Node(3);
	obj.root.right.right.right = new Node(9);
  	
	//Test execution
	obj.root = obj.delete_node(9);
	obj.root = obj.delete_node(2);
	obj.root = obj.delete_node(-1);
}
main();

Output

 Before delete leaf key 9 is
 Tree Element
 10 6 2 9 3 8 7 -1 2 9
 After delete leaf key 9 is
 Tree Element
 10 6 2 3 8 7 -1 2

 Before delete leaf key 2 is
 Tree Element
 10 6 2 3 8 7 -1 2
 After delete leaf key 2 is
 Tree Element
 10 6 3 8 7 -1

 Before delete leaf key -1 is
 Tree Element
 10 6 3 8 7 -1
 After delete leaf key -1 is
 Tree Element
 10 6 3 8 7
#  Python 3 Program 
#  Delete leaf node with given value

# Binary Tree node
class Node :
	
	def __init__(self, data) :
		# set node value
		self.data = data
		self.left = None
		self.right = None
	

class BinaryTree :
	
	status = False
	def __init__(self) :
		# set initial tree root to null
		self.root = None
	
	# Recursive function
	# Display preorder view of binary tree
	def pre_order(self, node) :
		if (node != None) :
			# Print node value
			print(" ", node.data, end = "")
			self.pre_order(node.left)
			self.pre_order(node.right)
		
	
	# Recursively process, deleting leaf nodes which equal to given key
	def delete_leaf_key(self, node, key) :
		if (node != None) :
			# Recursive execute, left and right subtree
			node.left = self.delete_leaf_key(node.left, key)
			node.right = self.delete_leaf_key(node.right, key)
			if (node.left == None and node.right == None and node.data == key) :
				# When get a deleted leaf node
				BinaryTree.status = True
				# This is deleted leaf node
				return None
			
			return node
		else :
			return None
		
	
	# This is used to handle the request of delete leaf nodes by given key
	def delete_node(self, key) :
		if (self.root == None) :
			print("\nEmpty Tree\n", end = "")
			return None
		else :
			#  Before delete, display tree elements
			print("\n Before delete leaf key ", key ," is ", end = "")
			print("\n Tree Element \n", end = "")
			self.pre_order(self.root)
			BinaryTree.status = False
			#  Deleting leaf by given key  
			self.root = self.delete_leaf_key(self.root, key)
			if (BinaryTree.status == True) :
				# When delete key is exist in leaves position
				print("\n After delete leaf key ", key ," is ", end = "")
				print("\n Tree Element \n", end = "")
				self.pre_order(self.root)
				print("\n", end = "")
			else :
				#  When deleted node not exist in leaves position 
				print("\n Leaf key ", key ," not exist\n", end = "")
			
			return self.root
		
	

def main() :
	# Make object 
	obj = BinaryTree()
	# 
	# 		    Construct Binary Tree
	# 		    -----------------------
	# 		          10
	# 		         /   \
	# 		        6     8
	# 		       / \   / \
	# 		      2   3 7   2
	# 		     /       \   \
	# 		    9        -1   9
	# 		
	
	# Add nodes
	obj.root = Node(10)
	obj.root.left = Node(6)
	obj.root.left.left = Node(2)
	obj.root.right = Node(8)
	obj.root.right.right = Node(2)
	obj.root.right.left = Node(7)
	obj.root.left.left.left = Node(9)
	obj.root.right.left.right = Node(-1)
	obj.root.left.right = Node(3)
	obj.root.right.right.right = Node(9)
	# Test execution
	obj.root = obj.delete_node(9)
	obj.root = obj.delete_node(2)
	obj.root = obj.delete_node(-1)

if __name__ == "__main__": main()

Output

 Before delete leaf key  9  is
 Tree Element
  10  6  2  9  3  8  7  -1  2  9
 After delete leaf key  9  is
 Tree Element
  10  6  2  3  8  7  -1  2

 Before delete leaf key  2  is
 Tree Element
  10  6  2  3  8  7  -1  2
 After delete leaf key  2  is
 Tree Element
  10  6  3  8  7  -1

 Before delete leaf key  -1  is
 Tree Element
  10  6  3  8  7  -1
 After delete leaf key  -1  is
 Tree Element
  10  6  3  8  7
#  Ruby Program 
#  Delete leaf node with given value

# Binary Tree node
class Node  
	# Define the accessor and reader of class Node  
	attr_reader :data, :left, :right
	attr_accessor :data, :left, :right
 
	def initialize(data) 
		# set node value
		self.data = data
		self.left = nil
		self.right = nil
	end
end
class BinaryTree  
	# Define the accessor and reader of class BinaryTree  
	attr_reader :root
	attr_accessor :root
	
	# indicator
	@@status = false
	def initialize() 
		# set initial tree root to null
		self.root = nil
	end
	# Recursive function
	# Display preorder view of binary tree
	def pre_order(node) 
		if (node != nil) 
			# Print node value
			print(" ", node.data)
			self.pre_order(node.left)
			self.pre_order(node.right)
		end
	end
	# Recursively process, deleting leaf nodes which equal to given key
	def delete_leaf_key(node, key) 
		if (node != nil) 
			# Recursive execute, left and right subtree
			node.left = self.delete_leaf_key(node.left, key)
			node.right = self.delete_leaf_key(node.right, key)
			if (node.left == nil && node.right == nil && node.data == key) 
				# When get a deleted leaf node
				@@status = true
				# This is deleted leaf node
				return nil
			end
			return node
		else 
			return nil
		end
	end
	# This is used to handle the request of delete leaf nodes by given key
	def delete_node(key) 
		if (self.root == nil) 
			print("\nEmpty Tree\n")
			return nil
		else 
			#  Before delete, display tree elements
			print("\n Before delete leaf key ", key ," is ")
			print("\n Tree Element \n")
			self.pre_order(self.root)
			@@status = false
			#  Deleting leaf by given key  
			self.root = self.delete_leaf_key(self.root, key)
			if (@@status == true) 
				# When delete key is exist in leaves position
				print("\n After delete leaf key ", key ," is ")
				print("\n Tree Element \n")
				self.pre_order(root)
				print("\n")
			else 
				#  When deleted node not exist in leaves position 
				print("\n Leaf key ", key ," not exist\n")
			end
			return root
		end
	end
end
def main() 
	# Make object 
	obj = BinaryTree.new()
	# 
	# 		    Construct Binary Tree
	# 		    -----------------------
	# 		          10
	# 		         /   \
	# 		        6     8
	# 		       / \   / \
	# 		      2   3 7   2
	# 		     /       \   \
	# 		    9        -1   9
	# 		
	
	# Add nodes
	obj.root = Node.new(10)
	obj.root.left = Node.new(6)
	obj.root.left.left = Node.new(2)
	obj.root.right = Node.new(8)
	obj.root.right.right = Node.new(2)
	obj.root.right.left = Node.new(7)
	obj.root.left.left.left = Node.new(9)
	obj.root.right.left.right = Node.new(-1)
	obj.root.left.right = Node.new(3)
	obj.root.right.right.right = Node.new(9)
	# Test execution
	obj.root = obj.delete_node(9)
	obj.root = obj.delete_node(2)
	obj.root = obj.delete_node(-1)
end
main()

Output

 Before delete leaf key 9 is 
 Tree Element 
 10 6 2 9 3 8 7 -1 2 9
 After delete leaf key 9 is 
 Tree Element 
 10 6 2 3 8 7 -1 2

 Before delete leaf key 2 is 
 Tree Element 
 10 6 2 3 8 7 -1 2
 After delete leaf key 2 is 
 Tree Element 
 10 6 3 8 7 -1

 Before delete leaf key -1 is 
 Tree Element 
 10 6 3 8 7 -1
 After delete leaf key -1 is 
 Tree Element 
 10 6 3 8 7
// Scala Program 
// Delete leaf node with given value

//Binary Tree node
class Node(var data: Int,
	var left: Node,
		var right: Node)
{
	def this(data: Int)
	{
		this(data, null, null);
	}
}
class BinaryTree(var root: Node,
	var status: Boolean)
{
	def this()
	{
		this(null, false);
	}
	//Recursive function
	//Display preorder view of binary tree
	def pre_order(node: Node): Unit = {
		if (node != null)
		{
			//Print node value
			print(" " + node.data);
			pre_order(node.left);
			pre_order(node.right);
		}
	}
	//Recursively process, deleting leaf nodes which equal to given key
	def delete_leaf_key(node: Node, key: Int): Node = {
		if (node != null)
		{
			//Recursive execute, left and right subtree
			node.left = delete_leaf_key(node.left, key);
			node.right = delete_leaf_key(node.right, key);
			if (node.left == null && node.right == null && node.data == key)
			{
				//When get a deleted leaf node
				status = true;
				//This is deleted leaf node
				return null;
			}
			return node;
		}
		else
		{
			return null;
		}
	}
	//This is used to handle the request of delete leaf nodes by given key
	def delete_node(key: Int): Node = {
		if (this.root == null)
		{
			print("\nEmpty Tree\n");
			return null;
		}
		else
		{
			// Before delete, display tree elements
			print("\n Before delete leaf key " + key + " is ");
			print("\n Tree Element \n");
			pre_order(this.root);
			status = false;
			// Deleting leaf by given key  
			this.root = delete_leaf_key(this.root, key);
			if (status == true)
			{
				//When delete key is exist in leaves position
				print("\n After delete leaf key " + key + " is ");
				print("\n Tree Element \n");
				pre_order(root);
				print("\n");
			}
			else
			{
				// When deleted node not exist in leaves position 
				print("\n Leaf key " + key + " not exist\n");
			}
			return root;
		}
	}
}
object Main
{
	def main(args: Array[String]): Unit = {
		//Make object 
		var obj: BinaryTree = new BinaryTree();
		/*
				    Construct Binary Tree
				    -----------------------
				          10
				         /   \
				        6     8
				       / \   / \
				      2   3 7   2
				     /       \   \
				    9        -1   9
				*/
		//Add nodes
		obj.root = new Node(10);
		obj.root.left = new Node(6);
		obj.root.left.left = new Node(2);
		obj.root.right = new Node(8);
		obj.root.right.right = new Node(2);
		obj.root.right.left = new Node(7);
		obj.root.left.left.left = new Node(9);
		obj.root.right.left.right = new Node(-1);
		obj.root.left.right = new Node(3);
		obj.root.right.right.right = new Node(9);
		//Test execution
		obj.root = obj.delete_node(9);
		obj.root = obj.delete_node(2);
		obj.root = obj.delete_node(-1);
	}
}

Output

 Before delete leaf key 9 is
 Tree Element
 10 6 2 9 3 8 7 -1 2 9
 After delete leaf key 9 is
 Tree Element
 10 6 2 3 8 7 -1 2

 Before delete leaf key 2 is
 Tree Element
 10 6 2 3 8 7 -1 2
 After delete leaf key 2 is
 Tree Element
 10 6 3 8 7 -1

 Before delete leaf key -1 is
 Tree Element
 10 6 3 8 7 -1
 After delete leaf key -1 is
 Tree Element
 10 6 3 8 7
// Swift 4 Program 
// Delete leaf node with given value

//Binary Tree node
class Node
{
	var data: Int;
	var left: Node? ;
	var right: Node? ;
	init(_ data: Int)
	{
		//set node value
		self.data = data;
		self.left = nil;
		self.right = nil;
	}
}
class BinaryTree
{
	var root: Node? ;
	//indicator
	var status: Bool = false;
	init()
	{
		//set initial tree root to null
		self.root = nil;
	}
	//Recursive function
	//Display preorder view of binary tree
	func pre_order(_ node: Node? )
	{
		if (node != nil)
		{
			//Print node value
			print(" ", node!.data, terminator: "");
			self.pre_order(node!.left);
			self.pre_order(node!.right);
		}
	}
	//Recursively process, deleting leaf nodes which equal to given key
	func delete_leaf_key(_ node: Node? , _ key : Int) -> Node?
	{
		if (node != nil)
		{
			//Recursive execute, left and right subtree
			node!.left = self.delete_leaf_key(node!.left, key);
			node!.right = self.delete_leaf_key(node!.right, key);
			if (node!.left == nil && node!.right == nil && node!.data == key)
			{
				//When get a deleted leaf node
				self.status = true;
				//This is deleted leaf node
				return nil;
			}
			return node;
		}
		else
		{
			return nil;
		}
	}
	//This is used to handle the request of delete leaf nodes by given key
	func delete_node(_ key: Int) -> Node?
	{
		if (self.root == nil)
		{
			print("\nEmpty Tree\n", terminator: "");
			return nil;
		}
		else
		{
			// Before delete, display tree elements
			print("\n Before delete leaf key ", key ," is ", terminator: "");
			print("\n Tree Element \n", terminator: "");
			self.pre_order(self.root);
			self.status = false;
			// Deleting leaf by given key  
			self.root = self.delete_leaf_key(self.root, key);
			if (self.status == true)
			{
				//When delete key is exist in leaves position
				print("\n After delete leaf key ", key ," is ", terminator: "");
				print("\n Tree Element \n", terminator: "");
				self.pre_order(self.root);
				print("\n", terminator: "");
			}
			else
			{
				// When deleted node not exist in leaves position 
				print("\n Leaf key ", key ," not exist\n", terminator: "");
			}
			return self.root;
		}
	}
}
func main()
{
	//Make object 
	let obj: BinaryTree = BinaryTree();
	/*
			    Construct Binary Tree
			    -----------------------
			          10
			         /   \
			        6     8
			       / \   / \
			      2   3 7   2
			     /       \   \
			    9        -1   9
			*/
	//Add nodes
	obj.root = Node(10);
	obj.root!.left = Node(6);
	obj.root!.left!.left = Node(2);
	obj.root!.right = Node(8);
	obj.root!.right!.right = Node(2);
	obj.root!.right!.left = Node(7);
	obj.root!.left!.left!.left = Node(9);
	obj.root!.right!.left!.right = Node(-1);
	obj.root!.left!.right = Node(3);
	obj.root!.right!.right!.right = Node(9);
	//Test execution
	obj.root = obj.delete_node(9);
	obj.root = obj.delete_node(2);
	obj.root = obj.delete_node(-1);
}
main();

Output

 Before delete leaf key  9  is
 Tree Element
  10  6  2  9  3  8  7  -1  2  9
 After delete leaf key  9  is
 Tree Element
  10  6  2  3  8  7  -1  2

 Before delete leaf key  2  is
 Tree Element
  10  6  2  3  8  7  -1  2
 After delete leaf key  2  is
 Tree Element
  10  6  3  8  7  -1

 Before delete leaf key  -1  is
 Tree Element
  10  6  3  8  7  -1
 After delete leaf key  -1  is
 Tree Element
  10  6  3  8  7




Comment

Please share your knowledge to improve code and content standard. Also submit your doubts, and test case. We improve by your feedback. We will try to resolve your query as soon as possible.

New Comment