Remove all leaf nodes from the binary search tree

Remove leaf nodes in binary search tree

Here given code implementation process.

//C Program 
//Remove all leaf nodes from the binary search tree
#include <stdio.h>
#include <stdlib.h>

//Structure of Binary Search Tree node
struct Node
{
  int data;
  struct Node *left,*right; 
};

//Adding a new node in binary search tree
void add( struct Node **root, int data)
{
  //Create a dynamic node of binary search tree 
  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; //Initially node left-pointer is NULL
    new_node->right = NULL;//Initially node right-pointer is NULL

    if(*root == NULL)
    {
      //When adds a first node in binary tree
      *root = new_node;
    }
    else
    {
      struct Node *find = *root;
      //iterate binary tree and add new node to proper position
      while(find != NULL)
      {
        if(find -> data > data)
        { 
          if(find->left==NULL)
          {
            find->left = new_node;
            break;
          }
          else
          { //visit left sub-tree
            find = find->left;
          }
        }
        else
        {
          if(find->right == NULL)
          {
            find->right = new_node;
            break;
          }
          else
          {
            //visit right sub-tree
            find = find->right;
          }
        }
      }
    }
  }else
  {
    printf("Memory Overflow\n");
    exit(0); //Terminate program execution
  }

}
struct Node* delete_node(struct Node*root)
{

  if(root!=NULL)
  {

    if(root->left == NULL && root->right == NULL)
    {
      //When find leaf node
      free(root);
      root=NULL;
      return NULL;
    }

    root->left=delete_node(root->left);

    root->right=delete_node(root->right);


    return root;
  }
  return NULL;
}
struct Node* delete_leaf(struct Node*root)
{
  if(root != NULL)
  {
    return  delete_node(root);
  }
  else
  {
    printf("\nEmpty BST\n");
    return NULL;
  }

}
void preorder(struct Node*root)
{
  if(root!=NULL)
  {
    printf("%3d ",root->data );
    preorder(root->left);
    preorder(root->right);
  }
}
int main()
{

  struct Node*root = NULL;

  //Add nodes in binary search tree
  /*
          6
        /    \
       /      \
      3        9
     /  \      / \
    1    5    8   11
   / \   /   /      \
 -3  2  4   7       15
                    /
                   12 
  */                


  add(&root,6); 
  add(&root,3); 
  add(&root,9); 
  add(&root,1); 
  add(&root,5); 
  add(&root,8); 
  add(&root,11); 
  add(&root,-3); 
  add(&root,2); 
  add(&root,7); 
  add(&root,15);
  add(&root,4); 

  add(&root,12); 
  preorder(root);
  root=delete_leaf(root);
  printf("\n After Delete Leaf\n");
  preorder(root);
  return 0;
}

Output

  6   3   1  -3   2   5   4   9   8   7  11  15  12 
 After Delete Leaf
  6   3   1   5   9   8  11  15
//C++ Program 
//Remove all leaf nodes from the binary search tree
#include <iostream>
using namespace std;

//ure of Binary Search Tree node
struct Node
{
  int data;
  Node *left,*right; 
};

class BST
{

public:
  Node*root;
  BST();
  //public methods
  void add(int);
  void preorder( Node*root);
  Node* delete_leaf();
  Node*  delete_node( Node*root);
};
BST::BST()
{
  root=NULL;
}
//Adding a new node in binary search tree
void BST :: add(int data)
{
  //Create a dynamic node of binary search tree 
   Node *new_node = new Node();

  if(new_node!=NULL)
  {
    //Set data and pointer values
    new_node->data = data;
    new_node->left = NULL; //Initially node left-pointer is NULL
    new_node->right = NULL;//Initially node right-pointer is NULL

    if(root == NULL)
    {
      //When adds a first node in binary tree
      root = new_node;
    }
    else
    {
       Node *find = root;

      //add new node to proper position
      while(find != NULL)
      {
        if(find -> data >= data)
        { 
          if(find->left==NULL)
          {
            find->left = new_node;
            break;
          }
          else
          { 
            //visit left sub-tree
            find = find->left;
          }
        }
        else
        {
          if(find->right == NULL)
          {
            find->right = new_node;
            break;
          }
          else
          {
            //visit right sub-tree
            find = find->right;
          }
        }
      }
    }
  }
  else
  {
    cout<<("Memory Overflow\n");
  }
}

Node* BST::  delete_node( Node*root)
{
    if (root!=NULL)
    {
      if (root->left == NULL && root->right == NULL)
      {
      //When find leaf node
        delete root;
        root=NULL;
        return NULL;
      }
      root->left=delete_node(root->left);
      root->right=delete_node(root->right);
      return root;
    }
    return NULL;
}
Node* BST:: delete_leaf()
{
    if (root != NULL)
    {
      root=delete_node(root);
    }
    else
    {
      cout<<"\nEmpty BST\n";
      return NULL;
    }
}
void BST:: preorder( Node*root)
{
    if (root!=NULL)
    {
      cout<<"  "<<root->data;
      preorder(root->left);
      preorder(root->right);
    }
}
int main()
{
  //Create object
  BST obj;

  //Add nodes in binary search tree
  /*
          6
        /    \
       /      \
      3        9
     /  \      / \
    1    5    8   11
   / \   /   /      \
 -3  2  4   7       15
                    /
                   12 
  */                


  obj.add(6); 
  obj.add(3); 
  obj.add(9); 
  obj.add(1); 
  obj.add(5); 
  obj.add(8); 
  obj.add(11); 
  obj.add(-3); 
  obj.add(2); 
  obj.add(7); 
  obj.add(15);
  obj.add(4); 

  obj.add(12); 
  obj.preorder(obj.root);
  obj.delete_leaf();
  cout<<("\n After Delete Leaf\n");
  obj.preorder(obj.root);

  return 0;
}

Output

  6  3  1  -3  2  5  4  9  8  7  11  15  12
 After Delete Leaf
  6  3  1  5  9  8  11  15
//Java program
//Remove all leaf nodes from the binary search tree
public class BST
{
  static class Node
  {
    int data;
    Node left,right;
  }
  public Node root;
  //Class constructors
  BST()
  {
    root=null;

  } 

  //insert  element
  public void add(int data)
  {
    //Create a dynamic node of binary search tree 
    Node new_node = new Node();

    if(new_node != null)
    {
      //Set data and pointer values
      new_node.data = data;
      //Initially node left-pointer is null
      new_node.left = null; 
      //Initially node right-pointer is null
      new_node.right = null;

      if(root == null)
      {
        //When adds a first node in binary tree
        root = new_node;
      }
      else
      {
        Node find = root;

        //add new node to proper position
        while(find != null)
        {
          if(find.data >= data)
          { 
            if(find.left==null)
            {
              find.left = new_node;
              break;
            }
            else
            { 
              //visit left sub-tree
              find = find.left;
            }
          }
          else
          {
            if(find.right == null)
            {
              find.right = new_node;
              break;
            }
            else
            {
            //visit right sub-tree
              find = find.right;
            }
          }
        }
      }
    }
    else
    {
      System.out.println("Memory Overflow");
    }
  }
  public Node delete_node( Node root)
  {
      if (root!=null)
      {
        if (root.left == null && root.right == null)
        {
        //When find leaf node
          root=null;
          return null;
        }
        root.left=delete_node(root.left);
        root.right=delete_node(root.right);
        return root;
      }
      return null;
  }
  public void delete_leaf()
  {
      if (root != null)
      {
        root=delete_node(root);
      }
      else
      {
        System.out.print("\nEmpty BST\n");
     
      }
  }
  public void  preorder( Node root)
  {
      if (root!=null)
      {
        System.out.print("  "+root.data);
        preorder(root.left);
        preorder(root.right);
      }
  }

  public static void main(String[] args) 
  {

    BST obj = new BST();

    //Add nodes in binary search tree
    /*
            6
          /    \
         /      \
        3        9
       /  \      / \
      1    5    8   11
     / \   /   /      \
   -3  2  4   7       15
                      /
                     12 
    */                


    obj.add(6); 
    obj.add(3); 
    obj.add(9); 
    obj.add(1); 
    obj.add(5); 
    obj.add(8); 
    obj.add(11); 
    obj.add(-3); 
    obj.add(2); 
    obj.add(7); 
    obj.add(15);
    obj.add(4); 

    obj.add(12); 
    obj.preorder(obj.root);
    obj.delete_leaf();
    System.out.print("\n After Delete Leaf\n");
    obj.preorder(obj.root);


  }
}

Output

  6  3  1  -3  2  5  4  9  8  7  11  15  12
 After Delete Leaf
  6  3  1  5  9  8  11  15
#Python Program 
#Remove all leaf nodes from the binary search tree
class Node:
  def __init__(self,data):
    self.data=data
    self.left=None
    self.right=None

   
class BST:

  def __init__(self):

    #Assign default value
    self.root=None
   
  #insert  element
  def add(self,data):

    #Create a dynamic node of binary search tree 
    new_node = Node(data)

    if(self.root == None):
      #When adds a first node in binary tree
      self.root = new_node
    
    else:
      find = self.root

      #add new node to proper position
      while(find != None):

        if(find.data >= data): 

          if(find.left==None):

            find.left = new_node
            break
          
          else: 

            #visit left sub-tree
            find = find.left
          
        
        else:

          if(find.right == None):

            find.right = new_node
            break
          
          else:

            #visit right sub-tree
            find = find.right
  
 
  def delete_node(self,root) :

    if (root!=None) :

      if (root.left == None  and  root.right == None) :

        #When find leaf node
        root=None
        return None
      root.left=self.delete_node(root.left)
      root.right=self.delete_node(root.right)
      return root
    return None
  def  delete_leaf(self) :

    if (self.root != None) :

      self.root=self.delete_node(self.root)
    else :

      print("\nEmpty BST\n")

      return None
  def preorder(self,root) :

    if (root!=None) :

      print(root.data,end="  ")

      self.preorder(root.left)
      self.preorder(root.right)


def main():

  #Make a object of BST class
  obj=  BST()


  #Add nodes in binary search tree
  #
  #          6
  #        /    \
  #       /      \
  #      3        9
  #     /  \      / \
  #    1    5    8   11
  #   / \   /   /      \
  # -3  2  4   7       15
  #                    /
  #                   12
  #  
  obj.add(6) 
  obj.add(3) 
  obj.add(9) 
  obj.add(1) 
  obj.add(5) 
  obj.add(8) 
  obj.add(11) 
  obj.add(-3) 
  obj.add(2) 
  obj.add(7) 
  obj.add(15)
  obj.add(4) 
  obj.add(12) 
  obj.preorder(obj.root)
  obj.delete_leaf()
  print("\n After Delete Leaf")

  obj.preorder(obj.root)

if __name__ =="__main__":
  main()

Output

6  3  1  -3  2  5  4  9  8  7  11  15  12  
 After Delete Leaf
6  3  1  5  9  8  11  15 
//C# program
//Remove all leaf nodes from the binary search tree
using System;
public class Node
{
  public int data;
  public Node left,right;
}
public class BST
{

  public Node root;
  //Class constructors
  BST()
  {
    root=null;

  } 

  //insert  element
  public void add(int data)
  {
    //Create a dynamic node of binary search tree 
    Node new_node = new Node();

    if(new_node != null)
    {
      //Set data and pointer values
      new_node.data = data;
      //Initially node left-pointer is null
      new_node.left = null; 
      //Initially node right-pointer is null
      new_node.right = null;

      if(root == null)
      {
        //When adds a first node in binary tree
        root = new_node;
      }
      else
      {
        Node find = root;

        //add new node to proper position
        while(find != null)
        {
          if(find.data >= data)
          { 
            if(find.left==null)
            {
              find.left = new_node;
              break;
            }
            else
            { 
              //visit left sub-tree
              find = find.left;
            }
          }
          else
          {
            if(find.right == null)
            {
              find.right = new_node;
              break;
            }
            else
            {
              //visit right sub-tree
              find = find.right;
            }
          }
        }
      }
    }
    else
    {
      Console.WriteLine("Memory Overflow");
    }
  }
  public Node delete_node( Node root)
  {
    if (root!=null)
    {
      if (root.left == null && root.right == null)
      {
        //When find leaf node
        root=null;
        return null;
      }
      root.left=delete_node(root.left);
      root.right=delete_node(root.right);
      return root;
    }
    return null;
  }
  public void delete_leaf()
  {
    if (root != null)
    {
      root=delete_node(root);
    }
    else
    {
      Console.Write("\nEmpty BST\n");

    }
  }
  public void  preorder( Node root)
  {
    if (root!=null)
    {
      Console.Write("  "+root.data);
      preorder(root.left);
      preorder(root.right);
    }
  }

  public static void Main(String[] args) 
  {

    BST obj = new BST();

    //Add nodes in binary search tree
    /*
            6
          /    \
         /      \
        3        9
       /  \      / \
      1    5    8   11
     / \   /   /      \
   -3  2  4   7       15
                      /
                     12 
    */                


    obj.add(6); 
    obj.add(3); 
    obj.add(9); 
    obj.add(1); 
    obj.add(5); 
    obj.add(8); 
    obj.add(11); 
    obj.add(-3); 
    obj.add(2); 
    obj.add(7); 
    obj.add(15);
    obj.add(4); 

    obj.add(12); 
    obj.preorder(obj.root);
    obj.delete_leaf();
    Console.Write("\n After Delete Leaf\n");
    obj.preorder(obj.root);


  }
}

Output

  6  3  1  -3  2  5  4  9  8  7  11  15  12
 After Delete Leaf
  6  3  1  5  9  8  11  15
<?php
//Php program 
//Remove all leaf nodes from the binary search tree
class Node
{
  public $data;
  public $left;
  public $right;
  function __construct($data)
  {
    $this->data = $data;
    $this->length = NULL;
    $this->right = NULL;
  }
}
class BST
{

  public $root;
  function __construct()
  {
    $root=NULL;
  }
  //Adding a new node in binary search tree
  public function add($data)
  {
    //Create a dynamic node of binary search tree 
    $new_node = new Node($data);

    if($this->root == NULL)
    {
      //When adds a first node in binary tree
      $this->root = $new_node;
    }
    else
    {
      $find = $this->root;

      //add new node to proper position
      while($find != NULL)
      {
        if($find->data >= $data)
        { 
          if($find->left==NULL)
          {
            $find->left = $new_node;
            break;
          }
          else
          { 
            //visit left sub-tree
            $find = $find->left;
          }
        }
        else
        {
          if($find->right == NULL)
          {
            $find->right = $new_node;
            break;
          }
          else
          {
            //visit right sub-tree
            $find = $find->right;
          }
        }
      }
    }

  }

  public function  delete_node($root)
  {
    if ($root!=NULL)
    {
      if ($root->left == NULL && $root->right == NULL)
      {
        //When find leaf node
        $root=NULL;
        return NULL;
      }
      $root->left=$this->delete_node($root->left);
      $root->right=$this->delete_node($root->right);
      return $root;
    }
    return NULL;
  }
  public function  delete_leaf()
  {
    if ($this->root != NULL)
    {
      $this->root=$this->delete_node($this->root);
    }
    else
    {
      echo "\nEmpty BST\n";
      return NULL;
    }
  }
  public function   preorder($root)
  {
    if ($root!=NULL)
    {
      echo "  ".$root->data;
      $this->preorder($root->left);
      $this->preorder($root->right);
    }
  }
}
function main()
{
  //Make a object of BST class
  $obj= new BST();


  //Add nodes in binary search tree
  /*
          6
        /    \
       /      \
      3        9
     /  \      / \
    1    5    8   11
   / \   /   /      \
 -3  2  4   7       15
                    /
                   12 
  
  */                
  $obj->add(6); 
  $obj->add(3); 
  $obj->add(9); 
  $obj->add(1); 
  $obj->add(5); 
  $obj->add(8); 
  $obj->add(11); 
  $obj->add(-3); 
  $obj->add(2); 
  $obj->add(7); 
  $obj->add(15);
  $obj->add(4); 

  $obj->add(12); 
  $obj->preorder($obj->root);
  $obj->delete_leaf();
  echo "\n After Delete Leaf\n";
  $obj->preorder($obj->root);


}
main();
?>

Output

  6  3  1  -3  2  5  4  9  8  7  11  15  12
 After Delete Leaf
  6  3  1  5  9  8  11  15


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







© 2021, kalkicode.com, All rights reserved