Skip to main content

Delete a path from given node to root node in BST

Delete a path from given node to root node

Here given code implementation process.

//C Program 
//Delete a path from given node to root node in BST
#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
  }

}

void swap_data(struct Node*root1,struct Node*root2)
{
  int temp=root2->data;
  root2->data=root1->data;
  root1->data=temp;
}
struct Node* delete_path(struct Node*root,int key)
{
  if(root != NULL)
  {
    if(root -> data > key)
    {
      root->left = delete_path(root->left,key);
    }
    else if(root->data < key)
    {
      root->right = delete_path(root->right,key);
    }
    struct Node*temp=NULL,*back=NULL;
    if(root->left==NULL)
    {
      temp=root;
      root=root->right;
    }
    else if(root->right==NULL)
    {
      temp=root;
      root=root->left;
    }
    else
    {
      temp=root->left;
      back=temp;

      while(temp->right!=NULL)
      {
        back=temp;
        temp=temp->right;
      }
      if(root->left==temp)
      {
        swap_data(root,temp);
        root->left=temp->left;
      }
      else
      {
        swap_data(root,temp);
        back->right=temp->left;
      }
    }

    if(temp!=NULL)
    {
      free(temp);
      temp=NULL;
    }
  }
  return root;
}
struct Node* find_node(struct Node*root,int key)
{
  if(root != NULL)
  {
    if(root -> data==key)
    {
      //when leaf node exist
      return root;
    }
    else if(root -> data > key)
    {
      return find_node(root->left,key);
    }
    else 
    {
      return find_node(root->right,key);
    }
  }
  return NULL;
}

struct Node* delete_node(struct Node*root,int key)
{
  if(root!=NULL)
  {

    if(find_node(root,key) != NULL)
    {
      root=delete_path(root,key);
    }
    else
    {
      printf("\n  Given node %d are not exist\n",key);
    }

  }
  else
  {
    printf("\n  Empty BST\n");
  }
  printf("\n");
  return root;
}
void inorder(struct Node*root)
{
  if(root!=NULL)
  {

    inorder(root->left);
    printf("%3d ",root->data );
    inorder(root->right);
  }
}
int main(){

  struct Node*root = NULL;

  //Add nodes in binary search tree
  /*
              5
            /   \ 
           /     \
          3       19
         / \     /   \
        2   4   8     31
       /       / \    /
      1       7   15  25   


  */                

  add(&root,5); 
  add(&root,3); 
  add(&root,19); 
  add(&root,2); 
  add(&root,4); 
  add(&root,8); 
  add(&root,31); 
  add(&root,1); 
  add(&root,7); 
  add(&root,25); 
  add(&root,15); 


  inorder(root);

  root=delete_node(root,31);
  inorder(root);
  return 0;
}

Output

  1   2   3   4   5   7   8  15  19  25  31 
  1   2   3   4   7   8  15  25
/*
 C++ Program
 Delete a path from given node to root node in BST
*/

#include<iostream>

using namespace std;
class Node {
public:
  int data;
  Node *left;
  Node *right;
  Node(int value) {
    this->data = value;
    this->left = NULL;
    this->right = NULL;
  }
};
class BinarySearchTree {
public:
  Node *root;
  BinarySearchTree() {
    this->root = NULL;
  }
  void add(int value) {
    Node *new_node = new Node(value);
    if (new_node != NULL) {
      if (this->root == NULL) {
        this->root = new_node;
      } else {
        Node *find = this->root;
        while (find != NULL) {
          if (find->data >= value) {
            if (find->left == NULL) {
              find->left = new_node;
              break;
            } else {
              find = find->left;
            }
          } else {
            if (find->right == NULL) {
              find->right = new_node;
              break;
            } else {
              find = find->right;
            }
          }
        }
      }
    } else {
      cout << "\nMemory Overflow\n";
    }
  }
  void inorder(Node *head) {
    if (head != NULL) {
      this->inorder(head->left);
      cout << head->data << "  ";
      this->inorder(head->right);
    }
  }
  void swap_data(Node *root1, Node *root2) {
    int temp = root2->data;
    root2->data = root1->data;
    root1->data = temp;
  }
  Node *delete_nodes(Node *head, int key) {
    if (head != NULL) {
      if (head->data > key) {
        head->left = this->delete_nodes(head->left, key);
      } else {
        head->right = this->delete_nodes(head->right, key);
      }
      Node *temp = NULL, *back = NULL;
      if (head->left == NULL) {
        temp = head;
        head = head->right;
      } else
      if (head->right == NULL) {
        temp = head;
        head = head->left;
      } else {
        temp = head->left;
        back = head;
        while (temp->right != NULL) {
          back = temp;
          temp = temp->right;
        }
        if (head->left == temp) {
          this->swap_data(head, temp);
          head->left = temp->left;
        } else {
          this->swap_data(head, temp);
          back->right = temp->left;
        }
      }
      temp = NULL;
    }
    return head;
  }
  Node *find_node(Node *head, int key) {
    if (head != NULL) {
      if (head->data == key) {
        return head;
      } else
      if (head->data > key) {
        return this->find_node(head->left, key);
      } else {
        return this->find_node(head->right, key);
      }
    }
    return NULL;
  }
  void delete_path(int key) {
    if (this->root != NULL) {
      if (this->find_node(this->root, key) != NULL) {
        this->root = this->delete_nodes(this->root, key);
      } else {
        cout << "\n  Given leaf node " << key << " are not exist\n";
      }
    } else {
      cout << "\n  Empty BST\n";
    }
    cout << "\n";
  }
};

int main() {
  BinarySearchTree obj;
  /*
              5
            /   \ 
           /     \
          3       19
         / \     /   \
        2   4   8     31
       /       / \    /
      1       7   15  25   


  */ 
  obj.add(5);
  obj.add(3);
  obj.add(19);
  obj.add(2);
  obj.add(4);
  obj.add(8);
  obj.add(31);
  obj.add(1);
  obj.add(7);
  obj.add(25);
  obj.add(15);
  obj.inorder(obj.root);
  obj.delete_path(31);
  /*
      After delete path 
      -----------------
                4
              /   \ 
             /     \
            3       15
           /      /   \
          2      8     25
         /      /     
        1      7        


    */
  obj.inorder(obj.root);
  return 0;
}

Output

  1   2   3   4   5   7   8  15  19  25  31 
  1   2   3   4   7   8  15  25
//Java program
//Delete a path from given node to root node in BST

//BST node
class Node {

  public int data;
  public Node left;
  public Node right;

  public Node(int value) {
    data = value;
    left = null;
    right = null;
  }
}
public class BinarySearchTree {


  public Node root;


  public BinarySearchTree() {
    root = null;

  }
  //insert a node in BST
  public void add(int value) {
    //Create a dynamic node of binary search tree 
    Node new_node = new Node(value);

    if (new_node != 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 >= value) {
            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.print("\nMemory Overflow\n");
    }
  }

  public void inorder(Node head) {
    if (head != null) {

      inorder(head.left);
      System.out.print(head.data + "  ");
      inorder(head.right);
    }
  }

  public void swap_data(Node root1, Node root2) {
    int temp = root2.data;
    root2.data = root1.data;
    root1.data = temp;
  }
  public Node delete_nodes(Node head, int key) {
    if (head != null) {
      if (head.data > key) {
        head.left = delete_nodes(head.left, key);
      } else {
        head.right = delete_nodes(head.right, key);
      }
      Node temp = null, back = null;
      if (head.left == null) {
        temp = head;
        head = head.right;
      } else if (head.right == null) {
        temp = head;
        head = head.left;
      } else {
        temp = head.left;
        back = head;
        while (temp.right != null) {
          back = temp;
          temp = temp.right;
        }
        if (head.left == temp) {
          swap_data(head, temp);
          head.left = temp.left;
        } else {
          swap_data(head, temp);
          back.right = temp.left;
        }
      }

      temp = null;

    }
    return head;
  }
  public Node find_node(Node head, int key) {
    if (head != null) {
      if (head.data == key) {
        //when leaf node exist
        return head;
      } else if (head.data > key) {
        return find_node(head.left, key);
      } else {
        return find_node(head.right, key);
      }
    }
    return null;
  }

  public void delete_path(int key) {
    if (root != null) {

      if (find_node(root, key) != null) {
        root = delete_nodes(root, key);
      } else {
        System.out.print("\n  Given leaf node " + key + " are not exist\n");
      }

    } else {
      System.out.print("\n  Empty BST\n");
    }
    System.out.print("\n");

  }

  public static void main(String[] args) {

    BinarySearchTree obj = new BinarySearchTree();
   //Add nodes in binary search tree
    /*
                5
              /   \ 
             /     \
            3       19
           / \     /   \
          2   4   8     31
         /       / \    /
        1       7   15  25   


    */                

    obj.add(5); 
    obj.add(3); 
    obj.add(19); 
    obj.add(2); 
    obj.add(4); 
    obj.add(8); 
    obj.add(31); 
    obj.add(1); 
    obj.add(7); 
    obj.add(25); 
    obj.add(15); 


    obj.inorder(obj.root);

    obj.delete_path(31);

     /*
      After delete path 
      -----------------
                4
              /   \ 
             /     \
            3       15
           /      /   \
          2      8     25
         /      /     
        1      7        


    */

    obj.inorder(obj.root);

  }
}

Output

  1   2   3   4   5   7   8  15  19  25  31 
  1   2   3   4   7   8  15  25
//C# program
//Delete a path from given node to root node in BST
using System;
//BST node
public class Node {

	public int data;
	public Node left;
	public Node right;

	public Node(int value) {
		data = value;
		left = null;
		right = null;
	}
}
public class BinarySearchTree {


	public Node root;


	public BinarySearchTree() {
		root = null;

	}
	//insert a node in BST
	public void add(int value) {
		//Create a dynamic node of binary search tree 
		Node new_node = new Node(value);

		if (new_node != 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 >= value) {
						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.Write("\nMemory Overflow\n");
		}
	}

	public void inorder(Node head) {
		if (head != null) {

			inorder(head.left);
			Console.Write(head.data + "  ");
			inorder(head.right);
		}
	}

	public void swap_data(Node root1, Node root2) {
		int temp = root2.data;
		root2.data = root1.data;
		root1.data = temp;
	}
	public Node delete_nodes(Node head, int key) {
		if (head != null) {
			if (head.data > key) {
				head.left = delete_nodes(head.left, key);
			} else {
				head.right = delete_nodes(head.right, key);
			}
			Node temp = null, back = null;
			if (head.left == null) {
				temp = head;
				head = head.right;
			} else if (head.right == null) {
				temp = head;
				head = head.left;
			} else {
				temp = head.left;
				back = head;
				while (temp.right != null) {
					back = temp;
					temp = temp.right;
				}
				if (head.left == temp) {
					swap_data(head, temp);
					head.left = temp.left;
				} else {
					swap_data(head, temp);
					back.right = temp.left;
				}
			}

			temp = null;

		}
		return head;
	}
	public Node find_node(Node head, int key) {
		if (head != null) {
			if (head.data == key) {
				//when leaf node exist
				return head;
			} else if (head.data > key) {
				return find_node(head.left, key);
			} else {
				return find_node(head.right, key);
			}
		}
		return null;
	}

	public void delete_path(int key) {
		if (root != null) {

			if (find_node(root, key) != null) {
				root = delete_nodes(root, key);
			} else {
				Console.Write("\n  Given leaf node " + key + " are not exist\n");
			}

		} else {
			Console.Write("\n  Empty BST\n");
		}
		Console.Write("\n");

	}

	public static void Main(String[] args) {

		BinarySearchTree obj = new BinarySearchTree();
		//Add nodes in binary search tree
		/*
                5
              /   \ 
             /     \
            3       19
           / \     /   \
          2   4   8     31
         /       / \    /
        1       7   15  25   


    */                

		obj.add(5); 
		obj.add(3); 
		obj.add(19); 
		obj.add(2); 
		obj.add(4); 
		obj.add(8); 
		obj.add(31); 
		obj.add(1); 
		obj.add(7); 
		obj.add(25); 
		obj.add(15); 


		obj.inorder(obj.root);

		obj.delete_path(31);

		/*
      After delete path 
      -----------------
                4
              /   \ 
             /     \
            3       15
           /      /   \
          2      8     25
         /      /     
        1      7        


    */

		obj.inorder(obj.root);

	}
}

Output

  1   2   3   4   5   7   8  15  19  25  31 
  1   2   3   4   7   8  15  25
#  Python 3 Program
#  Delete a path from given node to root node in BST

class Node :

  def __init__(self, value) :
    self.data = value
    self.left = None
    self.right = None
  

class BinarySearchTree :
  
  def __init__(self) :
    self.root = None
  
  def add(self, value) :
    new_node = Node(value)
    if (new_node != None) :
      if (self.root == None) :
        self.root = new_node
      else :
        find = self.root
        while (find != None) :
          if (find.data >= value) :
            if (find.left == None) :
              find.left = new_node
              break
            else :
              find = find.left
            
          else :
            if (find.right == None) :
              find.right = new_node
              break
            else :
              find = find.right
            
          
        
      
    else :
      print("\nMemory Overflow\n")
    
  
  def inorder(self, head) :
    if (head != None) :
      self.inorder(head.left)
      print(head.data ,end="  ")
      self.inorder(head.right)
    
  
  def swap_data(self, root1, root2) :
    temp = root2.data
    root2.data = root1.data
    root1.data = temp
  
  def delete_nodes(self, head, key) :
    if (head != None) :
      if (head.data > key) :
        head.left = self.delete_nodes(head.left, key)
      else :
        head.right = self.delete_nodes(head.right, key)
      
      temp = None
      back = None
      if (head.left == None) :
        temp = head
        head = head.right
      elif (head.right == None) :
        temp = head
        head = head.left
      else :
        temp = head.left
        back = head
        while (temp.right != None) :
          back = temp
          temp = temp.right
        
        if (head.left == temp) :
          self.swap_data(head, temp)
          head.left = temp.left
        else :
          self.swap_data(head, temp)
          back.right = temp.left
        
      
      temp = None
    
    return head
  
  def find_node(self, head, key) :
    if (head != None) :
      if (head.data == key) :
        return head
      elif (head.data > key) :
        return self.find_node(head.left, key)
      else :
        return self.find_node(head.right, key)
      
    
    return None
  
  def delete_path(self, key) :
    if (self.root != None) :
      if (self.find_node(self.root, key) != None) :
        self.root = self.delete_nodes(self.root, key)
      else :
        print("\n  Given leaf node ", key ," are not exist\n")
      
    else :
      print("\n  Empty BST\n")
    print()
 
  
def main() :
  obj = BinarySearchTree()
  #
  #              5
  #            /   \
  #           /     \
  #          3       19
  #         / \     /   \
  #        2   4   8     31
  #       /       / \    /
  #      1       7   15  25
  #  
  obj.add(5)
  obj.add(3)
  obj.add(19)
  obj.add(2)
  obj.add(4)
  obj.add(8)
  obj.add(31)
  obj.add(1)
  obj.add(7)
  obj.add(25)
  obj.add(15)
  obj.inorder(obj.root)
  obj.delete_path(31)
  #
  #      After delete path
  #                4
  #              /   \
  #             /     \
  #            3       15
  #           /      /   \
  #          2      8     25
  #         /      /
  #        1      7
  #    
  obj.inorder(obj.root)
  

if __name__ == "__main__":
  main()

Output

  1   2   3   4   5   7   8  15  19  25  31 
  1   2   3   4   7   8  15  25
# Ruby Program
# Delete a path from given node to root node in BST

class Node 
	attr_reader :data, :left, :right
	attr_accessor :data, :left, :right
	def initialize(value) 
		@data = value
		@left = nil
		@right = nil
	end
end

class BinarySearchTree 
	attr_reader :root
	attr_accessor :root
	def initialize() 
		@root = nil
	end
	def add(value) 
		new_node = Node.new(value)
		if (new_node != nil) 
			if (@root == nil) 
				@root = new_node
			else 
				find = @root
				while (find != nil) 
					if (find.data >= value) 
						if (find.left == nil) 
							find.left = new_node
							break
						else 
							find = find.left
						end
					else 
						if (find.right == nil) 
							find.right = new_node
							break
						else 
							find = find.right
						end
					end
				end
			end
		else 
			print("\nMemory Overflow\n")
		end
	end
	def inorder(head) 
		if (head != nil) 
			self.inorder(head.left)
			print(head.data ,"  ")
			self.inorder(head.right)
		end
	end
	def swap_data(root1, root2) 
		temp = root2.data
		root2.data = root1.data
		root1.data = temp
	end
	def delete_nodes(head, key) 
		if (head != nil) 
			if (head.data > key) 
				head.left = self.delete_nodes(head.left, key)
			else 
				head.right = self.delete_nodes(head.right, key)
			end
			temp = nil
			back = nil
			if (head.left == nil) 
				temp = head
				head = head.right
			elsif (head.right == nil) 
				temp = head
				head = head.left
			else 
				temp = head.left
				back = head
				while (temp.right != nil) 
					back = temp
					temp = temp.right
				end
				if (head.left == temp) 
					self.swap_data(head, temp)
					head.left = temp.left
				else 
					self.swap_data(head, temp)
					back.right = temp.left
				end
			end
			temp = nil
		end
		return head
	end
	def find_node(head, key) 
		if (head != nil) 
			if (head.data == key) 
				return head
			elsif (head.data > key) 
				return self.find_node(head.left, key)
			else 
				return self.find_node(head.right, key)
			end
		end
		return nil
	end
	def delete_path(key) 
		if (@root != nil) 
			if (self.find_node(@root, key) != nil) 
				@root = self.delete_nodes(@root, key)
			else 
				print("\n  Given leaf node ", key ," are not exist\n")
			end
		else 
			print("\n  Empty BST\n")
		end
		print("\n")
	end
end

def main() 
	obj = BinarySearchTree.new()
	#
	#              5
	#            /   \
	#           /     \
	#          3       19
	#         / \     /   \
	#        2   4   8     31
	#       /       / \    /
	#      1       7   15  25
	# 
	obj.add(5)
	obj.add(3)
	obj.add(19)
	obj.add(2)
	obj.add(4)
	obj.add(8)
	obj.add(31)
	obj.add(1)
	obj.add(7)
	obj.add(25)
	obj.add(15)
	obj.inorder(obj.root)
	obj.delete_path(31)
	#
	#      After delete path
	#                4
	#              /   \
	#             /     \
	#            3       15
	#           /      /   \
	#          2      8     25
	#         /      /
	#        1      7
	#   
	obj.inorder(obj.root)
end
main()

Output

  1   2   3   4   5   7   8  15  19  25  31 
  1   2   3   4   7   8  15  25
<?php
/*
  Php Program
  Delete a path from given node to root node in BST
*/

class Node {
  public $data;
  public $left;
  public $right;

  function __construct($value) {
    $this->data = $value;
    $this->left = null;
    $this->right = null;
  }
}
class BinarySearchTree {
  public $root;

  function __construct() {
    $this->root = null;
  }
  public  function add($value) {
    $new_node = new Node($value);
    if ($new_node != null) {
      if ($this->root == null) {
        $this->root = $new_node;
      } else {
        $find = $this->root;
        while ($find != null) {
          if ($find->data >= $value) {
            if ($find->left == null) {
              $find->left = $new_node;
              break;;
            } else {
              $find = $find->left;
            }
          } else {
            if ($find->right == null) {
              $find->right = $new_node;
              break;;
            } else {
              $find = $find->right;
            }
          }
        }
      }
    } else {
      echo("\nMemory Overflow\n");
    }
  }
  public  function inorder($head) {
    if ($head != null) {
      $this->inorder($head->left);
      echo($head->data ."  ");
      $this->inorder($head->right);
    }
  }
  public  function swap_data($root1, $root2) {
    $temp = $root2->data;
    $root2->data = $root1->data;
    $root1->data = $temp;
  }
  public  function delete_nodes($head, $key) {
    if ($head != null) {
      if ($head->data > $key) {
        $head->left = $this->delete_nodes($head->left, $key);
      } else {
        $head->right = $this->delete_nodes($head->right, $key);
      }
      $temp = null;
      $back = null;
      if ($head->left == null) {
        $temp = $head;
        $head = $head->right;
      } else
      if ($head->right == null) {
        $temp = $head;
        $head = $head->left;
      } else {
        $temp = $head->left;
        $back = $head;
        while ($temp->right != null) {
          $back = $temp;
          $temp = $temp->right;
        }
        if ($head->left == $temp) {
          $this->swap_data($head, $temp);
          $head->left = $temp->left;
        } else {
          $this->swap_data($head, $temp);
          $back->right = $temp->left;
        }
      }
      $temp = null;
    }
    return $head;
  }
  public  function find_node($head, $key) {
    if ($head != null) {
      if ($head->data == $key) {
        return $head;
      } else
      if ($head->data > $key) {
        return $this->find_node($head->left, $key);
      } else {
        return $this->find_node($head->right, $key);
      }
    }
    return null;
  }
  public  function delete_path($key) {
    if ($this->root != null) {
      if ($this->find_node($this->root, $key) != null) {
        $this->root = $this->delete_nodes($this->root, $key);
      } else {
        echo("\n  Given leaf node ". $key ." are not exist\n");
      }
    } else {
      echo("\n  Empty BST\n");
    }
    echo("\n");
  }
}
function main() {
  $obj = new BinarySearchTree();
  /*
          5
        /   \ 
       /     \
      3       19
     / \     /   \
    2   4   8     31
   /       / \    /
  1       7   15  25   


  */ 
  $obj->add(5);
  $obj->add(3);
  $obj->add(19);
  $obj->add(2);
  $obj->add(4);
  $obj->add(8);
  $obj->add(31);
  $obj->add(1);
  $obj->add(7);
  $obj->add(25);
  $obj->add(15);
  $obj->inorder($obj->root);
  $obj->delete_path(31);

  /*
      After delete path 
      -----------------
                4
              /   \ 
             /     \
            3       15
           /      /   \
          2      8     25
         /      /     
        1      7        


  */
  $obj->inorder($obj->root);
}
main();

Output

  1   2   3   4   5   7   8  15  19  25  31 
  1   2   3   4   7   8  15  25
/*
	Node Js Program
	Delete a path from given node to root node in BST
*/

class Node {

	constructor(value) {
		this.data = value;
		this.left = null;
		this.right = null;
	}
}
class BinarySearchTree {
	
	constructor() {
		this.root = null;
	}
	add(value) {
		var new_node = new Node(value);
		if (new_node != null) {
			if (this.root == null) {
				this.root = new_node;
			} else {
				var find = this.root;
				while (find != null) {
					if (find.data >= value) {
						if (find.left == null) {
							find.left = new_node;
							break;;
						} else {
							find = find.left;
						}
					} else {
						if (find.right == null) {
							find.right = new_node;
							break;;
						} else {
							find = find.right;
						}
					}
				}
			}
		} else {
			process.stdout.write("\nMemory Overflow\n");
		}
	}
	inorder(head) {
		if (head != null) {
			this.inorder(head.left);
			process.stdout.write(head.data + "  ");
			this.inorder(head.right);
		}
	}
	swap_data(root1, root2) {
		var temp = root2.data;
		root2.data = root1.data;
		root1.data = temp;
	}
	delete_nodes(head, key) {
		if (head != null) {
			if (head.data > key) {
				head.left = this.delete_nodes(head.left, key);
			} else {
				head.right = this.delete_nodes(head.right, key);
			}
			var temp = null;
			var back = null;
			if (head.left == null) {
				temp = head;
				head = head.right;
			} else
			if (head.right == null) {
				temp = head;
				head = head.left;
			} else {
				temp = head.left;
				back = head;
				while (temp.right != null) {
					back = temp;
					temp = temp.right;
				}
				if (head.left == temp) {
					this.swap_data(head, temp);
					head.left = temp.left;
				} else {
					this.swap_data(head, temp);
					back.right = temp.left;
				}
			}
			temp = null;
		}
		return head;
	}
	find_node(head, key) {
		if (head != null) {
			if (head.data == key) {
				return head;
			} else
			if (head.data > key) {
				return this.find_node(head.left, key);
			} else {
				return this.find_node(head.right, key);
			}
		}
		return null;
	}
	delete_path(key) {
		if (this.root != null) {
			if (this.find_node(this.root, key) != null) {
				this.root = this.delete_nodes(this.root, key);
			} else {
				process.stdout.write("\n  Given leaf node " + key + " are not exist\n");
			}
		} else {
			process.stdout.write("\n  Empty BST\n");
		}
		process.stdout.write("\n");
	}
}

function main() {
	var obj = new BinarySearchTree();
	/*
	          5
	        /   \ 
	       /     \
	      3       19
	     / \     /   \
	    2   4   8     31
	   /       / \    /
	  1       7   15  25   


	*/ 
	obj.add(5);
	obj.add(3);
	obj.add(19);
	obj.add(2);
	obj.add(4);
	obj.add(8);
	obj.add(31);
	obj.add(1);
	obj.add(7);
	obj.add(25);
	obj.add(15);
	obj.inorder(obj.root);
	obj.delete_path(31);
	/*
      After delete path 
      -----------------
                4
              /   \ 
             /     \
            3       15
           /      /   \
          2      8     25
         /      /     
        1      7        


    */
	obj.inorder(obj.root);
}


main();

Output

  1   2   3   4   5   7   8  15  19  25  31 
  1   2   3   4   7   8  15  25
/*
  Swift 4 Program
  Delete a path from given node to root node in BST
*/

class Node {
  var data: Int;
  var left: Node? ;
  var right: Node? ;
  init(_ value: Int) {
    self.data = value;
    self.left = nil;
    self.right = nil;
  }
}
class BinarySearchTree {
  var root: Node? ;
  init() {
    self.root = nil;
  }
  func add(_ value: Int) {
    let new_node: Node? = Node(value);
    if (new_node != nil) {
      if (self.root == nil) {
        self.root = new_node;
      } else {
        var find: Node? = self.root;
        while (find != nil) {
          if (find!.data >= value) {
            if (find!.left == nil) {
              find!.left = new_node;
              break;
            } else {
              find = find!.left;
            }
          } else {
            if (find!.right == nil) {
              find!.right = new_node;
              break;
            } else {
              find = find!.right;
            }
          }
        }
      }
    } else {
      print("\nMemory Overflow\n");
    }
  }
  func inorder(_ head: Node? ) {
    if (head != nil) {
      self.inorder(head!.left);
      print(head!.data ,terminator: "  ");
      self.inorder(head!.right);
    }
  }
  func swap_data(_ root1: Node? , _ root2 : Node? ) {
    let temp: Int = root2!.data;
    root2!.data = root1!.data;
    root1!.data = temp;
  }
  func delete_nodes(_ nodeSet: Node? , _ key : Int) -> Node? {
    var head: Node? = nodeSet;
    if (nodeSet != nil) {
      if (nodeSet!.data > key) {
        nodeSet!.left = self.delete_nodes(nodeSet!.left, key);
      } else {
        nodeSet!.right = self.delete_nodes(nodeSet!.right, key);
      }
      var temp: Node? = nil;
      var back: Node? = nil;
      
      if (head!.left == nil) {
        temp = head;
        head = head!.right;
      } else
      if (head!.right == nil) {
        temp = head;
        head = head!.left;
      } else {
        temp = head!.left;
        back = head;
        while (temp!.right != nil) {
          back = temp;
          temp = temp!.right;
        }
        if (head!.left === temp) {
          self.swap_data(head, temp);
          head!.left = temp!.left;
        } else {
          self.swap_data(head, temp);
          back!.right = temp!.left;
        }
      }
      temp = nil;
    }
    return head;
  }
  func find_node(_ head: Node? , _ key : Int) -> Node? {
    if (head != nil) {
      if (head!.data == key) {
        return head;
      } else
      if (head!.data > key) {
        return self.find_node(head!.left, key);
      } else {
        return self.find_node(head!.right, key);
      }
    }
    return nil;
  }
  func delete_path(_ key: Int) {
    if (self.root != nil) {
      if (self.find_node(self.root, key) != nil) {
        self.root = self.delete_nodes(self.root, key);
      } else {
        print("\n  Given leaf node ", key ," are not exist\n");
      }
    } else {
      print("\n  Empty BST\n");
    }
    print("\n");
  }
}
func main() {
  let obj: BinarySearchTree = BinarySearchTree();
  /*
              5
            /   \ 
           /     \
          3       19
         / \     /   \
        2   4   8     31
       /       / \    /
      1       7   15  25   


  */ 
  obj.add(5);
  obj.add(3);
  obj.add(19);
  obj.add(2);
  obj.add(4);
  obj.add(8);
  obj.add(31);
  obj.add(1);
  obj.add(7);
  obj.add(25);
  obj.add(15);
  obj.inorder(obj.root);
  obj.delete_path(31);
  /*
      After delete path 
      -----------------
                4
              /   \ 
             /     \
            3       15
           /      /   \
          2      8     25
         /      /     
        1      7        


    */
  obj.inorder(obj.root);
}
main();

Output

  1   2   3   4   5   7   8  15  19  25  31 
  1   2   3   4   7   8  15  25




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