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:
- Traverse the binary tree to find the node with the given value.
- Check if the node is a leaf node, i.e., it has no children.
- If the node is a leaf node, delete it from the tree.
- 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
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