AllAlgorithms · abranhe · Oct 6, 2020 · Oct 2, 2018 · Oct 3, 2018
diff --git a/BinaryTrees-traversals/BinaryTree.java b/BinaryTrees-traversals/BinaryTree.java
@@ -0,0 +1,58 @@
+/**
+ * Binary Tree Traversals implementation in Java
+ * 
+ * @author: {Sudheer Reddy T}
+ * @github: {tadipatrisudheerreddy}
+ */
+
+
+public class BinaryTree {
+
+	 public static TreeNode mirrorTree(TreeNode node){
+		if(node == null) 
+			return node;
+
+		TreeNode left = mirrorTree(node.left);
+		TreeNode right = mirrorTree(node.right);
+		node.left = right;
+		node.right = left;
+
+		return node;
+	}
+
+	 public static void main(String[] args){
+
+		TreeNode root = new TreeNode(8);
+		TreeNode.insert(root, new TreeNode(31));
+		TreeNode.insert(root, new TreeNode(45));
+		TreeNode.insert(root, new TreeNode(16));
+		TreeNode.insert(root, new TreeNode(24));
+		TreeNode.insert(root, new TreeNode(19));
+		TreeNode.insert(root, new TreeNode(29));
+		TreeNode.insert(root, new TreeNode(7));
+
+		StringBuffer inorderbuf=new StringBuffer();
+		StringBuffer preorderbuf=new StringBuffer();
+		StringBuffer postorderbuf=new StringBuffer();
+
+
+		TreeTraversal.getInorder(root,inorderbuf);
+		TreeTraversal.getPreorder(root, preorderbuf);
+		TreeTraversal.getPostorder(root, postorderbuf);
+
+		System.out.println("Before mirroring,In order tree is: "+inorderbuf);
+
+		BinaryTree.mirrorTree(root);
+
+		StringBuffer inorderbufAfter = new StringBuffer();
+		TreeTraversal.getInorder(root, inorderbufAfter);
+		System.out.println("After mirroring,In order tree is: "+inorderbufAfter);
+
+		System.out.println("Post order traversal:" + postorderbuf);
+		System.out.println("Pre order traversal:"+ preorderbuf);
+
+		System.out.println("Nodes with no siblings:");
+		TreeWithNoSiblings.printOnlyLeaves(root);
+
+	 }
+}
diff --git a/BinaryTrees-traversals/LowestCommonAncestor.java b/BinaryTrees-traversals/LowestCommonAncestor.java
@@ -0,0 +1,50 @@
+/**
+ * To find Lowest Common Ancestor for a binary tree implementation in Java
+ * 
+ * @author: {Sudheer Reddy T}
+ * @github: {tadipatrisudheerreddy}
+ */
+
+public  class LowestCommonAncestor {
+
+	TreeNode root;
+
+	public TreeNode LCA(int p,int q){
+		return findLCA(root,p,q);
+	}
+
+	private TreeNode findLCA(TreeNode root, int p, int q) {
+		if(root == null)
+			return null;
+		if(root.value == p || root.value == q)
+			return root;
+
+		TreeNode left = findLCA(root.left,p,q);
+		TreeNode right = findLCA(root.right,p,q);
+
+		if(left!=null && right!=null)
+			return root;
+
+		return left!=null? left : right;
+	}
+
+
+
+	public static void main(String[] args){
+
+		LowestCommonAncestor lca = new LowestCommonAncestor(); 
+
+		TreeNode root	 = new TreeNode(1);
+		root.left		 = new TreeNode(2);
+        root.right 		 = new TreeNode(3);
+        root.left.left   = new TreeNode(4);
+        root.left.right  = new TreeNode(5);
+        root.right.left  = new TreeNode(6);
+        root.right.right = new TreeNode(7);
+
+
+		System.out.println("Lowest Common Ancestor of (4,5): "+ lca.findLCA(root, 4, 5).value);
+		System.out.println("Lowest Common Ancestor of (4,6): "+ lca.findLCA(root, 4, 6).value);
+		System.out.println("Lowest Common Ancestor of (3,4): "+ lca.findLCA(root, 3, 4).value);
+	}
+}
diff --git a/BinaryTrees-traversals/SubTree.java b/BinaryTrees-traversals/SubTree.java
@@ -0,0 +1,64 @@
+/**
+ * Binary Tree Identical implementation in Java
+ * 
+ * @author: {Sudheer Reddy T}
+ * @github: {tadipatrisudheerreddy}
+ */
+public class SubTree {
+
+	TreeNode root1, root2;
+
+	public boolean isIdentical(TreeNode root1,TreeNode root2){
+
+		//Since every null tree is also subset of main tree
+		if(root1==null&&root2==null)
+			return true;
+		//Need to check the null condition only once,since we are using recursion at second time it should not be null 
+		if(root1==null&&root2==null)
+			return false;		
+
+	return (root1.value==root2.value)&& (isIdentical(root1.left,root2.left))
+			&&((isIdentical(root1.right,root2.right)) );
+	}
+
+	public boolean isSubTree(TreeNode p, TreeNode q){
+
+		//Since every null tree is also subset of main tree
+		if(q==null)
+			return true;
+
+		if(p==null)
+			return false;
+
+		if(isIdentical(p,q))
+			return true;
+
+	return isSubTree(p.left,q)||isSubTree(p.right,q);
+	}
+
+
+	public static void main(String[] args) {
+
+		SubTree tree = new SubTree();
+
+		TreeNode root1 = new TreeNode(26);
+		root1.right    = new TreeNode(3);
+		root1.right.right = new TreeNode(3);
+		root1.left = new TreeNode(10);
+		root1.left.left = new TreeNode(4);
+		root1.left.left.right = new TreeNode(30);
+		root1.left.right = new TreeNode(6);
+
+		TreeNode root2 = new TreeNode(10);
+		root2.right = new TreeNode(6);
+		root2.left  = new TreeNode(4);
+		root2.left.right = new TreeNode(30);
+
+		if(tree.isSubTree(tree.root1,tree.root2))
+			System.out.println("Tree2 is subtree of Tree1");
+		else
+			System.out.println("Tree2 is not a subtree of Tree1");
+
+	}
+
+}
diff --git a/BinaryTrees-traversals/TreeNode.java b/BinaryTrees-traversals/TreeNode.java
@@ -0,0 +1,40 @@
+/**
+ * Binary Tree Node implementation in Java
+ * 
+ * @author: {Sudheer Reddy T}
+ * @github: {tadipatrisudheerreddy}
+ */
+
+public class TreeNode {
+
+	 int value;
+	 TreeNode left;
+	 TreeNode right;
+
+	 public TreeNode(int i) {
+		 value = i;
+		 left = right = null;
+	 }
+
+	 public static boolean insert(TreeNode root,TreeNode n){
+		if(n!=null){
+			if(n.value >= root.value){
+				if(root.right==null){
+					root.right=n;
+					return true;
+				}
+				else
+					return insert(root.right,n);
+			}
+			else if(root.left==null){
+				root.left=n;
+				return true;
+			}
+			else
+				return insert(root.left,n);
+		} 
+		 return false;
+
+	 }
+
+}
diff --git a/BinaryTrees-traversals/TreeTraversal.java b/BinaryTrees-traversals/TreeTraversal.java
@@ -0,0 +1,33 @@
+/**
+ * Binary Tree Traversals implementation in Java
+ * 
+ * @author: {Sudheer Reddy T}
+ * @github: {tadipatrisudheerreddy}
+ */
+
+public class TreeTraversal {
+
+	public static  void getInorder(TreeNode node,StringBuffer buf){
+		if(node == null)
+			return;
+		getInorder(node.left,buf);
+		buf.append(" "+node.value);
+		getInorder(node.right,buf);
+	}
+
+	public static void getPreorder(TreeNode node,StringBuffer buf){
+		if(node==null)
+			return;
+		buf.append(" "+node.value);
+		getPreorder(node.left,buf);
+		getPreorder(node.right,buf);
+	}
+
+	public static void getPostorder(TreeNode node,StringBuffer buf){
+		if(node==null)
+			return;
+		getPostorder(node.left,buf);
+		getPostorder(node.right,buf);
+		buf.append(" "+node.value);
+	}
+}
diff --git a/BinaryTrees-traversals/TreeWithNoSiblings.java b/BinaryTrees-traversals/TreeWithNoSiblings.java
@@ -0,0 +1,38 @@
+/**
+ * To find the Tree with no siblings -  implementation in Java
+ * 
+ * @author: {Sudheer Reddy T}
+ * @github: {tadipatrisudheerreddy}
+ */
+
+public class TreeWithNoSiblings {
+	public static void printOnlyLeaves(TreeNode node){
+		if(node!=null){
+
+			printOnlyLeaves(node.left);
+
+			if ((node.left==null) && (node.right!=null))
+				System.out.println("Node with no sibling in right side is: " + node.right.value);
+
+			if((node.left!=null) && (node.right==null))
+				System.out.println("Node with no sibling in left side is: " + node.left.value);
+
+			printOnlyLeaves(node.right);
+		}		
+	}
+
+	public static void main(String[] args){
+
+		 TreeNode root = new TreeNode(50);
+		 TreeNode.insert(root, new TreeNode(30)); 
+		 TreeNode.insert(root, new TreeNode(60));
+		 TreeNode.insert(root, new TreeNode(22)); 
+		 TreeNode.insert(root, new TreeNode(38)); 
+		 TreeNode.insert(root, new TreeNode(55));
+		 TreeNode.insert(root, new TreeNode(34)); 
+
+
+		 TreeWithNoSiblings.printOnlyLeaves(root);
+	}
+
+}