fork download
copy 
  1.  
  2. /**
  3.  * Node Class of Tree
  4.  * @author Prateek
  5.  *
  6.  */
  7. class Node implements Comparable<Node> {
  8. 	public Node left;
  9. 	public int data;
  10. 	public Node right;
  11.  
  12. 	public Node(int val)
  13. 	{
  14. 		this.data=val;
  15. 	}
  16.  
  17. 	@Override
  18. 	public int compareTo(Node that) {
  19. 		return this.data - that.data ;
  20. 	}
  21.  
  22. 	@Override
  23. 	public String toString(){
  24. 		return this.data + "";
  25. 	}
  26.  
  27. }
  28.  
  29. /**
  30.  * BST operations
  31.  * @author Prateek
  32.  */
  33. class TreeOperations {
  34.  
  35. 	public Node startnode;
  36.  
  37. 	// ---------------------------------------- Insert Node in Tree
  38.  
  39. 	// Using recursion
  40. 	public void recinsert(Node root, int val) {
  41. 		if (val < root.data)	    {
  42. 			if (root.left != null)
  43. 				recinsert(root.left, val);
  44. 			else
  45. 				root.left = new Node(val);
  46. 		} 
  47. 		else if (val > root.data)	    {
  48. 			if (root.right != null)
  49. 				recinsert(root.right, val);
  50. 			else
  51. 				root.right = new Node(val);
  52. 		}
  53. 	}
  54.  
  55. 	public void insert(int val) {
  56. 		insert( val, startnode) ;
  57. 	}
  58.  
  59. 	// using non-recursion
  60. 	public void insert(int val, Node root) {
  61. 		Node newNode = new Node(val);
  62.  
  63. 		// if tree is null
  64. 		if (root == null){
  65. 			root = newNode;
  66. 			startnode = newNode; // saving root in static variable
  67. 		}
  68.  
  69. 		else {
  70. 			Node parent = null;
  71. 			Node child = root;
  72.  
  73. 			while (true) {
  74. 				parent = child;
  75.  
  76. 				// Move left
  77. 				if (newNode.data < child.data) { // Move left
  78. 					child = child.left;
  79. 					if (child == null) {
  80. 						parent.left = newNode;
  81. 						return;
  82. 					}
  83.  
  84. 					// Move Right
  85. 				} else {
  86. 					child = child.right;
  87. 					if (child == null) {
  88. 						parent.right = newNode;
  89. 						return;
  90.  
  91. 					}
  92. 				}
  93. 			}
  94. 		}
  95. 	}
  96.  
  97. 	// ---------------------------------------- Delete Node in Tree ------------------------------
  98. 	public boolean deleteNode(int val) {
  99.  
  100. 		if(startnode==null)
  101. 			return false;
  102.  
  103.  
  104. 		Node current=startnode;
  105. 		Node parent=startnode;
  106. 		boolean isLeftChild=true;
  107.  
  108. 		// Find the node Logic Starts Here
  109. 		while(current.data!=val){
  110.  
  111. 			parent=current;
  112.  
  113. 			if(val <current.data){
  114. 				isLeftChild=true;
  115. 				current = current.left;
  116. 			}
  117.  
  118. 			else 
  119. 			{
  120. 				isLeftChild=false;
  121. 				current =current.right;
  122. 			}
  123.  
  124. 			if(current==null)
  125. 				return false;
  126. 		}
  127.  
  128. 		//Node to be deleted found and stored in current
  129.  
  130. 		//Case 1: No childs of current
  131. 		if(current.left == null && current.right == null)
  132. 		{
  133. 			if(current==startnode)
  134. 				startnode=null;
  135. 			else
  136. 			{
  137. 				if(isLeftChild)
  138. 					parent.left=null;
  139. 				else
  140. 					parent.right=null;
  141. 			}
  142. 		}
  143.  
  144. 		// Case 2a: No left child
  145. 		else if(current.left == null ){
  146.  
  147. 			if(current==startnode)
  148. 				startnode=current.right;
  149.  
  150. 			else{
  151. 				if(isLeftChild)
  152. 					parent.left = current.right;
  153. 				else
  154. 					parent.right = current.right;
  155. 			}
  156. 		}
  157.  
  158. 		//Case 2b: No right child
  159. 		else if(current.right == null){
  160. 			if(current == startnode)
  161. 				startnode=current.left;
  162. 			else{
  163. 				if(isLeftChild)
  164. 					parent.left=current.left;
  165. 				else
  166. 					parent.right=current.left;
  167. 			}
  168. 		}
  169.  
  170. 		//Case 3 both children
  171. 		else {
  172.  
  173. 			Node successor = current.right;
  174. 			while (successor.left != null)
  175. 				successor = successor.left;
  176.  
  177. 			//Case 3a: Successor is right child of node to be deleted
  178. 			if(current.right==successor)
  179. 			{
  180. 				successor.left=current.left;
  181.  
  182. 				if(current==startnode)
  183. 					startnode=successor;
  184. 				else
  185. 				{
  186.  
  187. 					if(isLeftChild)
  188. 						parent.left=successor;
  189. 					else
  190. 						parent.right=successor;
  191. 				}
  192. 			}
  193. 			// Case 3b: Successor is not the right child of node to be deleted but in the right sub-tree
  194. 			else
  195. 			{
  196. 				Node successorParent=getSuccessorParent(current);
  197. 				successorParent.left= successor.right;
  198.  
  199. 				if(current==startnode)
  200. 					startnode=successor;
  201. 				else
  202. 				{
  203. 					if(isLeftChild)
  204. 						parent.left=successor;
  205. 					else
  206. 						parent.right=successor;
  207. 				}
  208. 				successor.left=current.left;
  209. 				successor.right=current.right;
  210. 			}
  211. 		}
  212. 		return true;
  213. 	}
  214.  
  215. 	//--------------------------------Parent of Inorder Successor ------------------------------------------------
  216. 	public Node getSuccessorParent(Node node){
  217. 		Node temp=node;
  218. 		temp=temp.right;
  219.  
  220. 		while(temp.left.left!=null)
  221. 			temp=temp.left;
  222.  
  223. 		return temp;
  224. 	}
  225.  
  226.  
  227.  
  228. 	// ---------------------------------------- Display Tree
  229. 	public void display() {
  230. 		display(startnode) ;
  231. 	}
  232.  
  233. 	public void display(Node root) {
  234. 		System.out.println("Inorder Traversal");
  235. 		inorder(root);
  236. 		//postorder(root);
  237. 		//preorder(root);
  238. 	}
  239.  
  240. 	public void inorder() {
  241. 		inorder(startnode);
  242. 	}
  243. 	public void inorder(Node root) {
  244. 		if (root != null) {
  245. 			inorder(root.left);
  246. 			System.out.print(root.data + "\t");
  247. 			inorder(root.right);
  248. 		}
  249. 	}
  250.  
  251. 	public void preorder() {
  252. 		preorder(startnode);
  253. 	}
  254. 	public void preorder(Node root) {
  255. 		if (root != null) {
  256. 			System.out.println(root.data);
  257. 			preorder(root.left);
  258. 			preorder(root.right);
  259. 		}
  260. 	}
  261.  
  262. 	public void postorder() {
  263. 		postorder(startnode);
  264. 	}
  265. 	public void postorder(Node root) {
  266. 		if (root != null) {
  267. 			postorder(root.left);
  268. 			postorder(root.right);
  269. 			System.out.println(root.data);
  270. 		}
  271. 	}
  272.  
  273.  
  274. 	//--------------------------- GET Predecessor ------------------------
  275. 	public Comparable getPredecessor(int val) {
  276. 		return getPredecessor(startnode, val );
  277. 	}
  278.  
  279. 	/**
  280. 	 * @param node of tree
  281. 	 * @return Predessor of a given Node
  282. 	 */
  283. 	public Comparable getPredecessor(Node root,int val) {
  284. 		if(root == null)
  285. 			return null;
  286.  
  287. 		Node pred = null;
  288. 		Node curr = root;
  289. 		while (curr!=null && curr.data != val) {
  290. 			// Move left
  291. 			if (val < curr.data) 
  292. 				curr = curr.left;
  293.  
  294. 			// Move Right
  295. 			else {
  296. 				pred = curr;
  297. 				curr = curr.right;
  298. 			}
  299. 		}
  300.  
  301. 		if(curr.left==null){
  302. 			return pred;
  303. 		}
  304. 		else
  305. 		{
  306. 			pred = curr.left;
  307. 			while (pred.right != null)
  308. 				pred = pred.right;
  309. 			return pred;
  310. 		}
  311.  
  312. 	}
  313.  
  314.  
  315. 	//--------------------------- GET Successor ------------------------
  316. 	public Comparable getSuccessor (int val) {
  317. 		return getSuccessor ( startnode , val) ;
  318. 	}
  319.  
  320. 	public Comparable getSuccessor (Node root , int val) {
  321. 		if(root == null)
  322. 			return null;
  323.  
  324. 		Node succ = null;
  325. 		Node curr = root;
  326. 		while (curr!=null && curr.data != val) {
  327. 			// Move Right
  328. 			if (val > curr.data) 
  329. 				curr = curr.right;
  330.  
  331. 			// Move left
  332. 			else {
  333. 				succ = curr;
  334. 				curr = curr.left;
  335. 			}
  336. 		}
  337.  
  338. 		if(curr.left==null){
  339. 			return succ;
  340. 		}
  341. 		else
  342. 		{
  343. 			succ = root.right;
  344. 			while (succ.left != null)
  345. 				succ = succ.left;
  346. 			return succ;
  347. 		}
  348. 	}
  349.  
  350. 	//-----------------------Get Minimum Value------------------------
  351. 	public int minValue(){
  352. 		return minValue(startnode);
  353. 	}
  354.  
  355.  
  356. 	/**
  357. 	 * Minimum value in the tree
  358. 	 * @param root of the tree
  359. 	 * @return
  360. 	 */
  361. 	public int minValue(Node root){
  362. 		if(root==null)
  363. 			return -1; // or return negative infinity
  364.  
  365. 		Node temp = root;
  366. 		while(temp.left !=null)
  367. 			temp=temp.left ;
  368.  
  369. 		return temp.data;
  370. 	}
  371.  
  372. 	//--------------------------Get Maximum Value-----------------------------
  373. 	public int maxValue(){
  374. 		return maxValue(startnode);
  375. 	}
  376.  
  377. 	/**
  378. 	 * Maximum value in the tree
  379. 	 * @param root of the tree
  380. 	 * @return
  381. 	 */
  382. 	public int maxValue(Node root){
  383. 		if(root==null)
  384. 			return -1; // or return negative infinity
  385.  
  386. 		Node temp = root;
  387. 		while(temp.right !=null)
  388. 			temp=temp.right ;
  389.  
  390. 		return temp.data;
  391. 	}
  392.  
  393.  
  394. 	//--------------------------- Has Path Sum-----------------------
  395. 	/**
  396. 	 * To find if the tree contains any path equal to given Sum
  397. 	 * @param root
  398. 	 * @param sum
  399. 	 * @return
  400. 	 */
  401. 	public boolean hasPathSum(Node root, int sum) {
  402. 		// return true if repeated differnce has reached to 0
  403. 		if (root == null) {
  404. 			return(sum == 0);
  405. 		}
  406. 		else {
  407. 			int subSum = sum - root.data;
  408. 			return(hasPathSum(root.left, subSum) || hasPathSum(root.right, subSum));
  409. 		}
  410. 	}
  411.  
  412. 	// ---------------------------- Contains Key ---------------------------------------
  413. 	public boolean contains(Comparable item) {
  414. 		return contains( item, startnode) ;
  415. 	}
  416.  
  417. 	public boolean contains(Comparable item, Node root) {
  418. 		Node temp = root;
  419.  
  420. 		while (temp != null) {
  421. 			int result = item.compareTo(temp.data);
  422.  
  423. 			if (result == 0)
  424. 				return true;
  425.  
  426. 			else if (result > 0)
  427. 				temp = temp.right;
  428.  
  429. 			else
  430. 				temp = temp.left;
  431. 		}
  432.  
  433. 		return false;
  434. 	}
  435.  
  436. 	//------------------------------ Recursive Contains Key-----------------------------------------
  437.  
  438. 	public boolean reccontains(Comparable item) {
  439. 		return reccontains( item, startnode) ;
  440. 	}
  441. 	/**
  442. 	 * IsContains
  443. 	 *
  444. 	 * @param item
  445. 	 * : Number to be searched
  446. 	 * @param root
  447. 	 * : Root of the tree
  448. 	 * @return true if contained in the tree, else false
  449. 	 */
  450. 	public boolean reccontains(Comparable item, Node root) {
  451.  
  452. 		if (root == null)
  453. 			return false;
  454.  
  455. 		int result = item.compareTo(root.data);
  456.  
  457. 		if (result < 0)
  458. 			return reccontains(item, root.left);
  459.  
  460. 		else if (result > 0)
  461. 			return reccontains(item, root.right);
  462.  
  463. 		else
  464. 			return true;
  465. 	}
  466.  
  467. 	// ---------------Recursive Get Operation----------------------
  468. 	public Comparable recGet(Comparable item ) {
  469. 		return recGet(item , startnode ) ;
  470. 	}
  471.  
  472. 	/**
  473. 	 * Recursive Get Operations
  474. 	 *
  475. 	 * @param item
  476. 	 * : Node object for which value is being searched
  477. 	 * @param root
  478. 	 * : root of the tree
  479. 	 * @return : -1 if not found or tree is null else return the value of the
  480. 	 * Node that was being searched
  481. 	 */
  482. 	public Comparable recGet(Comparable item, Node root) {
  483. 		if (root == null)
  484. 			return -1;
  485.  
  486. 		if (item.compareTo(root.data) < 0)
  487. 			return recGet(item, root.left); // retrieve from left subtree
  488. 		else if (item.compareTo(root.data) > 0)
  489. 			return recGet(item, root.right); // retrieve from right subtree
  490. 		else
  491. 			return root.data;
  492. 	}
  493.  
  494. 	//--------------------------height of Tree-------------------------------
  495.  
  496. 	public void height() {
  497. 		int h = height(startnode);
  498. 		System.out.println("Height of Tree is: " + h);
  499. 	}
  500.  
  501. 	/**
  502. 	 * Height (recursively)
  503. 	 * @param root
  504. 	 * @return
  505. 	 */
  506. 	public int height(Node root) {
  507. 		if (root == null)
  508. 			return 0;
  509. 		else {
  510. 			int lHeight = height(root.left);
  511. 			int rHeight = height(root.right);
  512.  
  513. 			if (lHeight > rHeight)
  514. 				return lHeight + 1;
  515. 			else
  516. 				return rHeight + 1;
  517.  
  518. 			// return max(height(node.left),height(node.right)) + 1
  519. 		}
  520. 	}
  521.  
  522.  
  523. 	// ---------------------- Level Order Traversal -----------------------------
  524. 	public void printLevelOrder() {
  525. 		int h = height(startnode);
  526. 		int i;
  527. 		for (i = 1; i <= h; i++) {
  528. 			int k = h - i;
  529. 			while (k != 0) {
  530. 				System.out.print("\t");
  531. 				k--;
  532. 			}
  533.  
  534. 			printGivenLevel(startnode, i);
  535. 			System.out.println();
  536. 		}
  537. 	}
  538.  
  539. 	// ---- Print all nodes at given level
  540. 	public void printGivenLevel(Node root, int level) {
  541.  
  542. 		if (root == null)
  543. 			return;
  544.  
  545. 		if (level == 1)
  546. 			System.out.print(root.data + "\t");
  547.  
  548. 		printGivenLevel(root.left, level - 1);
  549. 		printGivenLevel(root.right, level - 1);
  550. 	}
  551.  
  552. 	// --------Common Ancestor --------------
  553. 	public Node commonAncestor(Node root, Node n1, Node n2) {
  554.  
  555. 		if (root == null)
  556. 			return null;
  557.  
  558. 		if (root == n1 || root == n2) {
  559. 			return root;
  560. 		}
  561.  
  562. 		Node left = commonAncestor(root.left, n1, n2);
  563. 		Node right = commonAncestor(root.right, n1, n2);
  564.  
  565. 		if ((left == n1 && right == n2) || (left == n1 && right == n2))
  566. 			return root;
  567.  
  568. 		return (left != null) ? left : right;
  569. 	}
  570.  
  571. 	// ------------------------kth Smallest Eleent----------------
  572. 	public int KthSmallest( int k){
  573. 		countSmallest=0;
  574. 		KthSmallest(startnode,k);
  575. 		return countSmallest;
  576. 	}
  577.  
  578. 	static int countSmallest = 0;
  579. 	public void KthSmallest(Node root, int k) {
  580.  
  581. 		if (root == null)
  582. 			return;
  583.  
  584. 		KthSmallest(root.left, k);
  585.  
  586. 		if (++countSmallest == k) {
  587. 			System.out.println(k + " th smallest element is : " + root.data);
  588. 			return;
  589. 		}
  590.  
  591. 		KthSmallest(root.right, k);
  592. 		return;
  593. 	}
  594.  
  595. 	// -------------kth largest element---------------------------
  596.  
  597. 	public int KthLargest( int k){
  598. 		countlargest=0;
  599. 		KthLargest(startnode,k);
  600. 		return countlargest;
  601. 	}
  602.  
  603. 	static int countlargest = 0;
  604. 	public void KthLargest(Node root, int k) {
  605.  
  606. 		if (root == null)
  607. 			return;
  608.  
  609. 		KthLargest(root.right, k);
  610.  
  611. 		if (++countlargest == k) {
  612. 			System.out.println(k + " th largest element is : " + root.data);
  613. 			return;
  614. 		}
  615.  
  616. 		KthLargest(root.left, k);
  617. 	}
  618.  
  619. 	// -------------------Size of Tree--------------------------
  620. 	public int size() {
  621. 		return size(startnode);
  622. 	}
  623.  
  624. 	public int size(Node root) {
  625. 		if (root == null)
  626. 			return 0;
  627. 		else
  628. 			return (size(root.left) + 1 + size(root.right));
  629. 	}
  630.  
  631.  
  632. 	// ----------------Mirrorring a Tree by creating a copy ----------------------
  633. 	public Node mirror() {
  634. 		return mirror(startnode) ;
  635. 	}
  636.  
  637. 	public Node mirror(Node root) {
  638.  
  639. 		if (root == null)
  640. 			return null;
  641.  
  642. 		Node newRoot = new Node(root.data);
  643. 		newRoot.left = mirror(root.right);
  644. 		newRoot.right = mirror(root.left);
  645.  
  646. 		return newRoot;
  647. 	}
  648.  
  649. 	//---------------Check if Binary Search Tree------------------------
  650. 	public boolean isBST() {
  651. 		return( isBST(startnode, Integer.MIN_VALUE, Integer.MAX_VALUE) );
  652. 	}
  653.  
  654. 	public boolean isBST(Node node, int min, int max) {
  655. 		if (node==null)
  656. 			return true;
  657.  
  658. 		if (node.data < min || node.data > max)
  659. 			return false;
  660.  
  661. 		boolean leftStatus = isBST(node.left, min, node.data - 1);
  662.  
  663. 		if (!leftStatus)
  664. 			return false;
  665.  
  666. 		boolean rightOk = isBST(node.right, node.data+1, max);
  667.  
  668. 		return rightOk;
  669.  
  670. 		// isBST(node.left, min, node.data - 1) && isBST(node.right, node.data+1, max)
  671. 	}
  672.  
  673.  
  674. 	public static void main(String[] args) {
  675. 		TreeOperations obj = new TreeOperations() ;
  676.  
  677. 		Node root=new Node(5);
  678.  
  679. 		obj.insert(15);
  680. 		obj.insert(5);
  681. 		obj.insert(16);
  682. 		obj.insert(3);
  683. 		obj.insert(12 );
  684. 		obj.insert(20);
  685. 		obj.insert(10);
  686. 		obj.insert(13);
  687. 		obj.insert(18);
  688. 		obj.insert(23);
  689. 		obj.insert(6);
  690. 		obj.insert(7);
  691.  
  692. 			obj.display();
  693. 		//System.out.println(obj.getPredecessor(15));
  694. 		// TRy other operations as well ;)
  695. 	}
  696. }
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
https://ideone.com/CBE8t4
language:
Java (12.0.1)
created:
10 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!