CareerCup

let inorder traversal of Tree is S1
inorder traversal of SubTree is S2
pre order traversal of Tree is S3
pre order traversal of Sub Tree is S4
now check if s2 is substring of s1 and s4 is substring of s3

I think we need to consider any two traversals.
Like inorder & preorder for both and then checking subsring.
OR
inorder & postorder
OR
preorder & postorder

i wasn't able to think of anything in the interview room but after coming out i realized.

{
public class BinaryTree {
	Integer content;
	BinaryTree left;
	BinaryTree right;

	@Override
	public String toString() {
		// program to return a string representation of this tree;
		return content + ((left == null) ? "" : left.toString())
				+ ((right == null) ? "" : right.toString());
	}
}

}
if you toString both Trees you can just check if one is a substring of the other

By subtree, shouldn't the subtree structure be also taken into consideration?

1. Search the root node of the subtree in the big tree.
2. For every node found,
2.a. traverse at the same time to see if the subtree matches the subtree found in the main
2.b. if found return true
3. Return false (not found)

The question doesn't say anything about any specific tree, son the assumption of the binary tree cannot be justified. An O(n) time, O(n) space algorithm would be :
1.Hash the tree nodes
2. Hash the subtree in the same hash and if there is any subtree node whose entry is not occupied, return 0 (i.e., not a subtree)
* n is the total number of nodes in the original tree

We can check for inorder traversal of both the tree simultaneously within the same function

Let us suppose we iterate the main tree in preorder traversal such that we have the head node of the subtree and the current node of the main tree to have the same values.

Now call the following function

bool SearchSubtree(tree * HeadMain , tree* HeadSubtree) // HeadMain->value = HeadSubtree->value

{
 If (!HeadSubtree) 
    return true;

 if ((HeadMain == NULL ||  HeadMain != HeadSubtree) && (HeadSubtree != NULL))
    return false;

if ((SearchSubtree(HeadMain->left , HeadSubtree->left)) == false)
    return false;

return (SearchSubtree(HeadMain->left , HeadSubtree->left)) == false) ;

}

So what I'm trying to do is
1)Check if the nodes do not match , subtree is not present
2)If the nodes match , check the left subtree of both
3)Then check the right subtree
4)Now we dont have to traverse the Main tree completely . Eg. We'll keep on calling the left child of the main tree recursively only to the point the left child of the subtree has been completely traversed . We recursively call back the previous nodes for both . In essence we are traversing only that part of the main tree which is concerned with the subtree .
5)Extra memory is saved from copying each elsement and checking them later
6)The complexity O(N) where n corresponds to the number of elements of the subtree

1.Hash the elements of the sub-tree (this save us some space if the original tree is very large)
2. Start mapping the elements of the original tree and increment the counter every time there is a match.
3. return true if counter=size_of_sub_tree, return false otherwise

just check

boolean foo(binNode root, binNode subtree_root){
	if(root!=null){
		if(root!=subtree_root)
			return foo(root.right,subtree_root)||foo(root.left, subtree_root);
		else return true;
	}else return false;

}