Find if a given tree is subtree of another huge tree

The problem statement is:


You have two very large binary trees: Tl , with millions of nodes, and T2, with
hundreds of nodes. Create an algorithm to decide if T2 is a subtree of Tl.
A tree T2 is a subtree of Tl if there exists a node n in Tl such that the subtree of n is identical to T2. That is, if you cut off the tree at node n, the two trees would be identical.

My implementation:

```
//Node of a Tree
static class TreeNode{
int data;
TreeNode left;
TreeNode right;
boolean visited;

public TreeNode(int data){
this.data = data;
left=right=null;
visited = false;
}

public boolean isVisited(){
return visited;
}
}

//The Tree
static class Tree{
TreeNode root;
}

//Node of a Generic LinkedList
static class LinkListNode{
T data;
LinkListNode next;

public LinkListNode(T data){
this.data = data;
}
}

//Generic LinkedList to store
//TreeNodes
static class LinkList{
LinkListNode head;

public boolean isEmpty(){
return head==null;
}

public T poll(){
if(!this.isEmpty()){
LinkListNode temp = head;
head = head.next;
return temp.data;
}else{
throw new UnsupportedOperationException();
}
}

public void add(T data){
if(head==null){
head = new LinkListNode(data);
}else{
LinkListNode temp = head;
while(temp.next!=null){
temp = temp.next;
}
temp.next = new LinkListNode(data);
}
}
}

//Cuts the first tree at the Node equal to second Tree's root
//So, if the second tree is subtree of first one, these two trees must
//be equal
public static TreeNode findUsingBFS(TreeNode myTreeNode, int required){
LinkList Queue = new LinkList();
Queue.add(myTreeNode);
boolean found = false;
TreeNode current = new TreeNode(-1);
while(! Queue.isEmpty()){
current = Queue.po

You should make use of existing libraries where you can. In this case, you can make use of java.util.LinkedList from the Collections API, and there is no need to go through the effort of creating your own linked list class.

Looking some more at your code, LinkedList might not do what you want. What you want is a Queue. That's why you called your variable that (LinkList Queue = new LinkList();). But there's also a java.util.Queue that you can use.

If you're concerned about memory usage, you should be able to reduce it slightly by getting rid of the boolean visited, because you never write to it.

For performance concerns, iterating a tree is not a whole lot different than iterating a list. They should both be \$O(n)\$. But your LinkedList implementation makes it \$O(n^2)\$.

Take a look:

public void add(T data){
    if(head==null){
        head = new LinkListNode(data);
    }else{
        LinkListNode temp = head;
        while(temp.next!=null){
            temp = temp.next;
        }
        temp.next = new LinkListNode(data);
    }
}

Whenever you add nodes to your queue, you start at the head and iterate over the nodes to get to the end!

That means, if we traverse a tree of 15 items (4 layers all filled), you..

1
   2       3
 4   5   6   7
8 9 A B C D E F

Get first node 1, make 2 the new head, attach 3 to 2 (2->3)
Poll 2, attach 4 to 3, iterate over 1 node (3->4->?) to add 5
Poll 3, iterate over 1 node (4->5->?) to add 6, iterate over 2 nodes to add 7
Poll 4, iterate over 2 nodes (5->6->7->?) to add 8, 3 nodes for 9,
Poll 5, 3 nodes for A, 4 nodes for B,
Poll 6, 4 nodes for C, 5 nodes for D,
Poll 7, 5 nodes for E, and 6 nodes for F.

In total you iterate over nodes needlessly 36 times. If I added another layer, making it a tree of 31 items, you'd needlessly iterate another 280 times. This adds up very, very fast.

If you keep a reference to the last node added, you can just get the tail node, make a new node, set that to tail's next, then set the tail reference to the new node.

And this is why you do not write your own LinkedList. Data structures are complex and it is easy to screw up or forget something. Use the built-ins so you can benefit from the help that already exists (many people use the generics, so if you have an issue, people know the library that you are using and can help you), and because it will do a better job than you will do. Besides, why write your own when you have a problem to solve?

Aside from all that, some generic comments:

//Cuts the first tree at the Node equal to second Tree's root
//So, if the second tree is subtree of first one, these two trees must
//be equal
public static TreeNode findUsingBFS(TreeNode myTreeNode, int required){

Use javadoc-style comments for method blocks, it allows IDEs to apply the documentation you write for usage during programming.

Looks like this:

/** 
 * Cuts the first tree at the Node equal to second Tree's root
 * So, if the second tree is subtree of first one, these two trees must
 * be equal
 */
public static TreeNode findUsingBFS(TreeNode myTreeNode, int required){

Right now, it doesn't add a whole lot, but you can add things like @param myTreeNode the treenode to start the search at or @returns the treenode containing the required data, or a new treenode containing -1 as data if it couldn't find the node. Then when you're in your IDE programming, it will tell you that the first parameter is "the treenode to start the search at" and the return value is "containing the required data, or a new treenode containing -1 as data if it couldn't find the node". And this can be really helpful.

if(current.left!=null)
    if(!current.left.isVisited()){

Ignoring the part where you don't use visited, if you are going to have two conditions like this without an else, just combine them to if(current.left!=null && !current.left.isVisited()). && shortcircuits, that is, if current.left is null, then it doesn't check the other condition and you will not get a NullPointerException.

if(first.data == second.data){
    isOK = true;
}else{
    isOK = false;
}

For this sort of stuff, isOK = first.data == second.data will do. Also, no need to put isOK all the way at the top if you're not going to use it until later. Put it where you are first going to use it instead. If you do that it makes the encapsulated conditional look a lot nicer:

boolean isOK = first.data == second.data;
return isOK && isEqual(first.left, second.left) && isEqual(first.right, second.right);

StackExchange Code Review Q#117325, answer score: 4