Java Program to Delete a Particular Node in a Tree Without Recursion

«
»
This is a Java Program to to delete a particular node from the tree without using recursion.

Here is the source code of the Java Program to Delete a Particular Node in a Tree Without Using Recursion. The Java program is successfully compiled and run on a Windows system. The program output is also shown below.

  1. //This is a java program to delete a particular node from the tree without using a recursion
  2. import java.util.Scanner;
  3.  
  4. class BinaryNode
  5. {
  6.     private int        Key;
  7.     private Object     Data;
  8.     private BinaryNode Left;
  9.     private BinaryNode Right;
  10.  
  11.     public BinaryNode(int k, Object d)
  12.     {
  13.         Key = k;
  14.         Data = d;
  15.         Left = null;
  16.         Right = null;
  17.     }
  18.  
  19.     // Get Operations
  20.     public int gKey()
  21.     {
  22.         return Key;
  23.     }
  24.  
  25.     public Object gData()
  26.     {
  27.         return Data;
  28.     }
  29.  
  30.     public BinaryNode gLeft()
  31.     {
  32.         return Left;
  33.     }
  34.  
  35.     public BinaryNode gRight()
  36.     {
  37.         return Right;
  38.     }
  39.  
  40.     // Set Operations
  41.     public void sKey(int AValue)
  42.     {
  43.         Key = AValue;
  44.     }
  45.  
  46.     public void sData(Object AValue)
  47.     {
  48.         Data = AValue;
  49.     }
  50.  
  51.     public void sLeft(BinaryNode AValue)
  52.     {
  53.         Left = AValue;
  54.     }
  55.  
  56.     public void sRight(BinaryNode AValue)
  57.     {
  58.         Right = AValue;
  59.     }
  60. }
  61.  
  62. public class BTree
  63. {
  64.     private BinaryNode Root;
  65.     private int        NoOfNodes;
  66.  
  67.     private BTree()
  68.     { // constructor
  69.         Root = null;
  70.         NoOfNodes = 0;
  71.     }
  72.  
  73.     public boolean IsEmpty()
  74.     {
  75.         return (NoOfNodes == 0);
  76.     }
  77.  
  78.     public BinaryNode gRoot()
  79.     {
  80.         return Root;
  81.     }
  82.  
  83.     public int Count()
  84.     {
  85.         return NoOfNodes;
  86.     }
  87.  
  88.     public int Size(BinaryNode ATree)
  89.     {
  90.         if (ATree == null)
  91.             return 0;
  92.         else
  93.             return (1 + Size(ATree.gLeft()) + Size(ATree.gRight()));
  94.     }
  95.  
  96.     public int Height(BinaryNode ATree)
  97.     {
  98.         if (ATree == null)
  99.             return 0;
  100.         else
  101.             return (1 + Math.max(Height(ATree.gLeft()), Height(ATree.gRight())));
  102.     }
  103.  
  104.     public void PreOrder(BinaryNode ATree)
  105.     {
  106.         if (ATree != null)
  107.         {
  108.             System.out.print(ATree.gKey() + " ");
  109.             PreOrder(ATree.gLeft());
  110.             PreOrder(ATree.gRight());
  111.         }
  112.     }
  113.  
  114.     public void InOrder(BinaryNode ATree)
  115.     {
  116.         if (ATree != null)
  117.         {
  118.             InOrder(ATree.gLeft());
  119.             System.out.print(ATree.gKey() + " ");
  120.             InOrder(ATree.gRight());
  121.         }
  122.     }
  123.  
  124.     public void PostOrder(BinaryNode ATree)
  125.     {
  126.         if (ATree != null)
  127.         {
  128.             PostOrder(ATree.gLeft());
  129.             PostOrder(ATree.gRight());
  130.             System.out.print(ATree.gKey() + " ");
  131.         }
  132.     }
  133.  
  134.     public void Insert(int AId, Object AValue)
  135.     {
  136.         BinaryNode Temp, Current, Parent;
  137.         if (Root == null)
  138.         {
  139.             Temp = new BinaryNode(AId, AValue);
  140.             Root = Temp;
  141.             NoOfNodes++;
  142.         } else
  143.  
  144.         {
  145.             Temp = new BinaryNode(AId, AValue);
  146.             Current = Root;
  147.             while (true)
  148.             {
  149.                 Parent = Current;
  150.                 if (AId < Current.gKey())
  151.                 {
  152.                     Current = Current.gLeft();
  153.                     if (Current == null)
  154.                     {
  155.                         Parent.sLeft(Temp);
  156.                         NoOfNodes++;
  157.                         return;
  158.                     }
  159.                 } else
  160.                 {
  161.                     Current = Current.gRight();
  162.                     if (Current == null)
  163.                     {
  164.                         Parent.sRight(Temp);
  165.                         NoOfNodes++;
  166.                         return;
  167.                     }
  168.                 }
  169.             }
  170.         }
  171.     }
  172.  
  173.     public BinaryNode Find(int AKey)
  174.     {
  175.         BinaryNode Current = null;
  176.         if (!IsEmpty())
  177.         {
  178.             Current = Root; // start search at top of tree
  179.             while (Current.gKey() != AKey)
  180.             {
  181.                 if (AKey < Current.gKey())
  182.                     Current = Current.gLeft();
  183.                 else
  184.                     Current = Current.gRight();
  185.                 if (Current == null)
  186.                     return null;
  187.             }
  188.         }
  189.         return Current;
  190.     }
  191.  
  192.     public BinaryNode GetSuccessor(BinaryNode ANode)
  193.     {
  194.         BinaryNode Current, Successor, SuccessorParent;
  195.         Successor = ANode;
  196.         SuccessorParent = ANode;
  197.         Current = ANode.gRight();
  198.         while (Current != null)
  199.         {
  200.             SuccessorParent = Successor;
  201.             Successor = Current;
  202.             Current = Current.gLeft();
  203.         }
  204.         if (Successor != ANode.gRight())
  205.         {
  206.             SuccessorParent.sLeft(Successor.gRight());
  207.             Successor.sRight(ANode.gRight());
  208.         }
  209.         return Successor;
  210.     }
  211.  
  212.     public boolean Delete(int AKey)
  213.     {
  214.         BinaryNode Current, Parent;
  215.         boolean IsLeftChild = true;
  216.         Current = Root;
  217.         Parent = Root;
  218.         while (Current.gKey() != AKey)
  219.         {
  220.             Parent = Current;
  221.             if (AKey < Current.gKey())
  222.             {
  223.                 IsLeftChild = true;
  224.                 Current = Current.gLeft();
  225.             } else
  226.             {
  227.                 IsLeftChild = false;
  228.                 Current = Current.gRight();
  229.             }
  230.             if (Current == null)
  231.                 return false;
  232.         }
  233.  
  234.         if (Current.gLeft() == null && Current.gRight() == null)
  235.         {
  236.             if (Current == Root)
  237.                 Root = Current.gLeft();
  238.             else if (IsLeftChild)
  239.                 Parent.sLeft(Current.gRight());
  240.             else
  241.                 Parent.sRight(Current.gRight());
  242.         }
  243.  
  244.         else
  245.         {
  246.             if (Current.gRight() == null)
  247.             {
  248.                 if (Current == Root)
  249.                     Root = Current.gRight();
  250.                 else if (IsLeftChild)
  251.                     Parent.sLeft(Current.gLeft());
  252.                 else
  253.                     Parent.sRight(Current.gLeft());
  254.             }
  255.  
  256.             else
  257.             {
  258.                 if (Current.gLeft() == null)
  259.                 {
  260.                     if (Current == Root)
  261.                         Root = Current.gLeft();
  262.                     else if (IsLeftChild)
  263.                         Parent.sLeft(Current.gRight());
  264.                     else
  265.                         Parent.sRight(Current.gRight());
  266.                 }
  267.  
  268.                 else
  269.                 {
  270.                     BinaryNode Successor = GetSuccessor(Current);
  271.                     if (Current == Root)
  272.                         Root = Successor;
  273.                     else if (IsLeftChild)
  274.                         Parent.sLeft(Successor);
  275.                     else
  276.                         Parent.sRight(Successor);
  277.                     Successor.sLeft(Current.gLeft());
  278.                 }
  279.             }
  280.         }
  281.         NoOfNodes--;
  282.         return true;
  283.     }
  284.  
  285.     public static void main(String[] Args)
  286.     {
  287.         BTree MyTree = new BTree();
  288.         BinaryNode NodeAt;
  289.  
  290.         System.out.println("Enter the elements in the tree");
  291.         int N = 5;
  292.         Scanner sc = new Scanner(System.in);
  293.         for (int i = 0; i < N; i++)
  294.             MyTree.Insert(sc.nextInt(), i);
  295.  
  296.         System.out.print("\nInorder  : ");
  297.         MyTree.InOrder(MyTree.gRoot());
  298.         System.out.print("\nPreorder  : ");
  299.         MyTree.PreOrder(MyTree.gRoot());
  300.         System.out.print("\nPostorder  : ");
  301.         MyTree.PostOrder(MyTree.gRoot());
  302.  
  303.         System.out.println("\nEnter the element to be deleted: ");
  304.         int delete = sc.nextInt();
  305.  
  306.         MyTree.Delete(delete);
  307.  
  308.         System.out.print("\nInorder  : ");
  309.         MyTree.InOrder(MyTree.gRoot());
  310.         System.out.print("\nPreorder  : ");
  311.         MyTree.PreOrder(MyTree.gRoot());
  312.         System.out.print("\nPostorder  : ");
  313.         MyTree.PostOrder(MyTree.gRoot());
  314.  
  315.         sc.close();
  316.     }
  317. }

Output:

advertisement
$ javac BTree.java
$ java BTree
 
Enter the elements in the tree
54 12 32 19 45 
 
Inorder  : 12 19 32 45 54 
Preorder  : 54 12 32 19 45 
Postorder  : 19 45 32 12 54 
 
Enter the element to be deleted: 
12
 
Inorder  : 19 32 45 54 
Preorder  : 54 32 19 45 
Postorder  : 19 45 32 54

Sanfoundry Global Education & Learning Series – 1000 Java Programs.

Note: Join free Sanfoundry classes at Telegram or Youtube
advertisement
advertisement

Here’s the list of Best Books in Java Programming, Data Structures and Algorithms.

advertisement
advertisement
Subscribe to our Newsletters (Subject-wise). Participate in the Sanfoundry Certification contest to get free Certificate of Merit. Join our social networks below and stay updated with latest contests, videos, internships and jobs!

Youtube | Telegram | LinkedIn | Instagram | Facebook | Twitter | Pinterest
Manish Bhojasia - Founder & CTO at Sanfoundry
Manish Bhojasia, a technology veteran with 20+ years @ Cisco & Wipro, is Founder and CTO at Sanfoundry. He lives in Bangalore, and focuses on development of Linux Kernel, SAN Technologies, Advanced C, Data Structures & Alogrithms. Stay connected with him at LinkedIn.

Subscribe to his free Masterclasses at Youtube & technical discussions at Telegram SanfoundryClasses.