fork download
copy 
  1. /**
  2.  * Node Class of Tree
  3.  * @author Prateek
  4.  *
  5.  */
  6. class Node implements Comparable<Node> {
  7. 	public Node left;
  8. 	public int data;
  9. 	public Node right;
  10.  
  11. 	public Node(int val)
  12. 	{
  13. 		this.data=val;
  14. 	}
  15.  
  16. 	@Override
  17. 	public int compareTo(Node that) {
  18. 		return this.data - that.data ;
  19. 	}
  20.  
  21. 	@Override
  22. 	public String toString(){
  23. 		return this.data + "";
  24. 	}
  25.  
  26. }
  27.  
  28. /**
  29.  * BST operations
  30.  * @author Prateek
  31.  */
  32.  class DeletionBST {
  33.  
  34. 	public static Node startnode;
  35.  
  36.  
  37. 	public void insert(int val) {
  38. 		insert( val,  startnode) ;
  39. 	}
  40.  
  41. 	// using non-recursion
  42. 	public void insert(int val, Node root) {
  43. 		Node newNode = new Node(val);
  44.  
  45. 		// if tree is null
  46. 		if (root == null){
  47. 			root = newNode;
  48. 			startnode = newNode;   // saving root in static variable
  49. 		}
  50.  
  51. 		else {
  52. 			Node parent = null;
  53. 			Node child = root;
  54.  
  55. 			while (true) {
  56. 				parent = child;
  57.  
  58. 				// Move left
  59. 				if (newNode.data < child.data) { // Move left
  60. 					child = child.left;
  61. 					if (child == null) {
  62. 						parent.left = newNode;
  63. 						return;
  64. 					}
  65.  
  66. 					// Move Right
  67. 				} else {
  68. 					child = child.right;
  69. 					if (child == null) {
  70. 						parent.right = newNode;
  71. 						return;
  72.  
  73. 					}
  74. 				}
  75. 			}
  76. 		}
  77. 	}
  78.  
  79. 	// ---------------------------------------- Delete Node in Tree ------------------------------
  80. 	public boolean deleteNode(int val) {
  81.  
  82. 		if(startnode==null)
  83. 			return false;
  84.  
  85.  
  86. 		Node current=startnode;
  87. 		Node parent=startnode;
  88. 		boolean isLeftChild=true;
  89.  
  90. 		// Find the node Logic Starts Here
  91. 		while(current.data!=val){
  92.  
  93. 			parent=current;
  94.  
  95. 			if(val <current.data){
  96. 				isLeftChild=true;
  97. 				current = current.left;
  98. 			}
  99.  
  100. 			else 
  101. 			{
  102. 				isLeftChild=false;
  103. 				current =current.right;
  104. 			}
  105.  
  106. 			if(current==null)
  107. 				return false;
  108. 		}
  109.  
  110. 		//Node to be deleted found and stored in current
  111.  
  112. 		//Case 1: No childs of current
  113. 		if(current.left == null && current.right == null)
  114. 		{
  115. 			if(current==startnode)
  116. 				startnode=null;
  117. 			else
  118. 			{
  119. 				if(isLeftChild)
  120. 					parent.left=null;
  121. 				else
  122. 					parent.right=null;
  123. 			}
  124. 		}
  125.  
  126. 		// Case 2a: No left child
  127. 		else if(current.left == null ){
  128.  
  129. 			if(current==startnode)
  130. 				startnode=current.right;
  131.  
  132. 			else{
  133. 				if(isLeftChild)
  134. 					parent.left = current.right;
  135. 				else
  136. 					parent.right = current.right;
  137. 			}
  138. 		}
  139.  
  140. 		//Case 2b: No right child
  141. 		else if(current.right == null){
  142. 			if(current == startnode)
  143. 				startnode=current.left;
  144. 			else{
  145. 				if(isLeftChild)
  146. 					parent.left=current.left;
  147. 				else
  148. 					parent.right=current.left;
  149. 			}
  150. 		}
  151.  
  152. 		//Case 3 both children
  153. 		else {
  154.  
  155. 			Node successor = (Node) getSuccessor(current);
  156.  
  157. 			//Case 3a: Successor is right child of node to be deleted
  158. 			if(current.right==successor)
  159. 			{
  160. 				successor.left=current.left;
  161.  
  162. 				if(current==startnode)
  163. 					startnode=successor;
  164. 				else
  165. 				{
  166.  
  167. 					if(isLeftChild)
  168. 						parent.left=successor;
  169. 					else
  170. 						parent.right=successor;
  171. 				}
  172. 			}
  173. 			// Case 3b: Successor is not the right child of node to be deleted but in the right sub-tree
  174. 			else
  175. 			{
  176. 				Node successorParent=getSuccessorParent(current);
  177. 				successorParent.left= successor.right;
  178.  
  179. 				if(current==startnode)
  180. 					startnode=successor;
  181. 				else
  182. 				{
  183. 					if(isLeftChild)
  184. 						parent.left=successor;
  185. 					else
  186. 						parent.right=successor;
  187. 				}
  188. 				successor.left=current.left;
  189. 				successor.right=current.right;
  190. 			}
  191. 		}
  192. 		return true;
  193. 	}
  194.  
  195. 	//--------------------------------Parent of Inorder Successor ------------------------------------------------
  196. 	public Node getSuccessorParent(Node node){
  197. 		Node temp=node;
  198. 		temp=temp.right;
  199.  
  200. 		while(temp.left.left!=null)
  201. 			temp=temp.left;
  202.  
  203. 		return temp;
  204. 	}
  205.  
  206. 	//--------------------------- GET Successor ------------------------
  207. 		public Comparable getSuccessor () {
  208. 			return getSuccessor ( startnode) ;
  209. 		}
  210.  
  211. 		public Comparable getSuccessor (Node root) {
  212. 			if(root == null)
  213. 				return null;
  214.  
  215. 			Node temp = root.right;
  216. 			while (temp.left != null)
  217. 				temp = temp.left;
  218. 			return temp;
  219. 		}
  220.  
  221. 	// ---------------------------------------- Display Tree ----------------------------------
  222. 	public void display() {
  223. 		display(startnode) ;
  224. 	}
  225.  
  226. 	public void display(Node root) {
  227. 		System.out.println("Inorder Traversal");
  228. 		inorder(root);
  229. 		//postorder(root);
  230. 		//preorder(root);
  231. 	}
  232.  
  233. 	public void inorder() {
  234. 		inorder(startnode);
  235. 	}
  236. 	public void inorder(Node root) {
  237. 		if (root != null) {
  238. 			inorder(root.left);
  239. 			System.out.print(root.data + "\t");
  240. 			inorder(root.right);
  241. 		}
  242. 	}
  243.  
  244. 	public static void main(String[] args) {
  245. 		DeletionBST obj = new DeletionBST() ;
  246.  
  247. 		Node root=new Node(15);
  248. 		startnode = root;
  249. 		obj.insert(5);
  250. 		obj.insert(16);
  251. 		obj.insert(3);
  252. 		obj.insert(12 );
  253. 		obj.insert(20);
  254. 		obj.insert(10);
  255. 		obj.insert(13);
  256. 		obj.insert(18);
  257. 		obj.insert(23);
  258. 		obj.insert(6);
  259. 		obj.insert(7);
  260. obj.display();
  261. 		obj.deleteNode(15);
  262. 		obj.display();
  263. 		obj.deleteNode(6);
  264. 		obj.display();
  265.  
  266.  
  267. 	}
  268. }
  269.  
Success #stdin #stdout 0.07s 380160KB
comments (?)
stdin
copy 
Standard input is empty
stdout
copy 
Inorder Traversal
3	5	6	7	10	12	13	15	16	18	20	23	Inorder Traversal
3	5	6	7	10	12	13	16	18	20	23	Inorder Traversal
3	5	7	10	12	13	16	18	20	23
https://ideone.com/Y0yKQx
language:
Java (12.0.1)
created:
11 years ago
visibility:
secret

Share or Embed source code

Discover > Sphere Engine API

The brand new service which powers Ideone!

Discover > IDE Widget

Widget for compiling and running the source code in a web browser!