CareerCup

Does each "L" or "R" traversal generate exactly one "p" one in the sequence? or do these "L" and "R" 's generate sequences of different lengths?

Some clarification : 100,70,90 imagine as a BST though the problem is not for a BST.then we have N(100) L(70) R(90).
O(n) means in almost one Tree traversal you should figure out the solution.

Its still not clear how multiples sequences can be generated for a given pattern.

please be clear about the problem

The algorithm will be as follows -

Maintain 2 list -> start_node_list
and end_node_list
For each node check if the pattern exist -> put the node in the start_node and put the end node in end_node_list.

Once all the nodes are traversed you will have a list of start nodes and end nodes.
now this problem reduces to finding the longest sequence of start and end nodes.

The algorithm is O(n|p|) = O(n)

First check at every node(we can do in order traversal) if the patterns exist.
If we find a pattern at any given node, we add that in array list

Lets define a new class
pair {
Node startnode
Node endnode
int length;}

Now when you find a pattern at a node say startnode to endnode.
Now adding part
if array list already have this startnode as any of the pair's endnode, increment the lenth of that pair by 1 and replace the endnode with new endnode.
else just add this new pair in array list
once done traverse the array list to find the max length.

this will be O(n+2m) n is no of nodes and m is number of sequences
so this is O(n)

Without even understanding the question people are posting their solution...
First of all the question is not clear.. someone explain the question first then we can think of the solutions

func(current,path[],pathlen)
{
if(path[]=string of pattern)
check with max, do as required.
if(curr->left!=NULL)
{path[pathlen++]=L;
func(curr->left,path,pathlen);
}
if(curr->right!=NULL)
{
path[pathlen++]=R;
func(curr->right,path,pathlen);
}
return;
}