CareerCup

No need to sort the array. Iterate on the array and find each element in the tree. Mark all the nodes visited during the traversal.

Use a hash to track the discovered numbers. O(g) extra space.
Time complexity : O(g+depth of tree)

public static boolean samePathGroup(Node node, int[] numbers) {
		if (node == null || numbers.length == 0) {
			return false;
		}
		
		Map<Integer, Boolean> hash = new HashMap<Integer, Boolean>();
		for (int i = 0; i< numbers.length;++i) {
			hash.put(numbers[i], Boolean.FALSE);
		}
		int count = 0, i = 0;
		Integer cur = numbers[0];
		while(node != null) {
			if (hash.get(cur)) { // already discovered
				if (++i == numbers.length) {
					break;
				}
				cur = numbers[i];
				continue; 
			}
			
			Integer curNodeVal = node.get();
			if (cur == curNodeVal) {
				hash.put(cur, Boolean.TRUE);
				++count;
				if (++i == numbers.length) {
					break;
				}
				cur = numbers[i];
				continue;
			} else if (cur < curNodeVal) {
				node = node.left();
			} else {
				node = node.right();
			}
			
			if (hash.containsKey(curNodeVal) && !hash.get(curNodeVal)) {
				++count;
				hash.put(curNodeVal, Boolean.TRUE);
			}
			
		}
		return (count == numbers.length);
}

1.Hash nodes of the bst in preorder, based on their ordering and not their values. This help prevent collision and also save us some space (e.g., if the range of the elements of nodes is very large)

void HashValuesPreOrder(struct bst *b, int hash[], int &index)
{
	if(b)
	{
		hash[index++]=b->data; //hashed by their order and not their vallues
		HashValuesPreOrder(b->lc,hash,index);
		HashValuesPreOrder(b->rc,hash,index);
	}
}

2.find the first element of the given array in the hash table:

int FindElement(int val,int hash[], int n)
{
	int h=val%n;
	if(hash[h]==val)
		return h;
	int pos=(h+1)%n;
	while(pos!=h-1)
	{
		if(hash[pos]==val)
			return pos;
		pos=(pos+1)%n;
	}
	return -1;
}

3. Check to see if the order of the elements of the array matches the order of the element of the hash, given the starting index of the first element of the array in the hash table:

int SamePathArrayElements(int a[], int hash[], int n)
{
	int i;
	int prev=-1;
	int pos=FindElement(a[0],hash,n+1);
	if(pos==-1)
		return 0;

	for(i=pos;i<sizeof(a)/sizeof(a[0]);i++)
	{
		if(hash[i]==a[i] && i==prev-1)
			prev=i;
		else 
			return 0;
	}

	return 1;
}

What do you mean by same path?
Inorder, preorder, postorder, path to leaf node, which path exactly?

Basic approach
1) Convert g (which I'll assume is an int[]) into an object of a new class, which I'll call ShrinkableOrderedList, which defines methods:

size()
   leftVal()  [min]
   rightVal()  [max]
   popLeft()  [remove min val]
   popRight()  [remove max val]

2) Write a simple tree descent algorithm that pops off one end or the other as it descends.
Call g.length "m".
Step 1 efficiency is O(m*log(m)).
Step 2 efficiency is max(O(m), O(log(n)), where log(n) is the depth of the tree.
One assumes that log(n) is much greater than m, so the overall performance is probably dominated by the size of the tree and is O(log(n)).

Code:

public boolean allOnSamePath(int[] g, Node tree) {
  ShrinkableOrderedList list = ShrinkableOrderedList.fromNumbers(g);
  return allOnSamePath(list, tree);
}

public boolean allOnSamePath(ShrinkableOrderedList list, Node node) {
  if (list.size() == 0)
    return true;
  if (node == null)
    return false;
  int nodeVal = node.key;
  if (list.rightVal() < nodeVal)
    return allOnSamePath(list, node.left);
  else if (list.rightVal() == nodeVal) {
    list.popRight();
    return allOnSamePath(list, node.left);
  } else if (list.leftVal() > nodeVal)
    return allOnSamePath(list, node.right);
  else if (list.leftVal() == nodeVal) {
    list.popLeft();
    return allOnSamePath(list, node.right);
  } else
    return false;
}

In case you're interested, here is an implementation of ShrinkableOrderedList:

class ShrinkableOrderedList
{
  private int[] values;
  private int leftI = 0;
  private int rightI = -1;

  public static ShrinkableOrderedList forValues(int[] ints) {
    ShrinkableOrderedList inst = new ShrinkableOrderedList(ints.length);
    Set<Integer> ordered = new TreeSet<Integer>();
    for (int i : ints)
      ordered.add(i);
    for (Integer i: ordered)
      inst.values[++inst.rightI] = i;
    inst.rightI--;
  }

  private ShrinkableOrderedList() {
    //private default constructor
  }

  private ShrinkableOrderedList(int len) {
    values = new int[len];
  }

  public int size() {
    return rightI - leftI + 1;
  }

  public int leftVal() {
    return values[leftI];
  }

  public int rightVal() {
    return values[rightI];
  }

  public void popLeft() {
    leftI++;
  }

  public void popRight() {
    rightI--;
  }
}

Let's talk in pseudocode:
Let |g| = m, |Tree| = n

1) Order "g" making it easier to search in it O(m*lg(m))
2) Have a "seen in g" boolean array of same size as g.

3) Do a DFS on the tree (preorder traversal):
If not a null pointer/reference:
a) When you are in a node, check if the current node's data
is in g via binary search.
b) If it is in g, then check if an ancestor has not already seen this element of g (that is, if "seen" is not already true). If not, this is the first node in current path could could have seen this, so set the corresponding flag to true.
c) Visit left child, visit right child
d) Unset the "seen" flag IF we are the ones who set it in b).
If DFS is passed a null pointer or reference:
Check the "seen" flags to see if they are all true... if so we have a match.

bool isOnSamePath(int nums[], Root* root)
{
	sortasc(nums);
	
	int smallest = smallest(nums);
	int greatest = greatest(nums);
	
	int val = root->getVal();
	int len = (lengthOf(nums)/2)-1;
	
	if(val > smallest && val < greatest && !existInList(val, nums))
	{
		return false; // The root breaks the path
	}
	
	if(val > smallest & val < greatest && existInList(val, nums))
	{
		int left[len], right[len];
		
		getLeftElemsOfval(left, nums, val);
		getRightElemsOfVal(right, nums, val);
	
		return isOnSamePath(isOnSamePath(left, root->getLeft())&& isOnSamePath(right, root->getRight());
	}
    if(val == greatest && root->getLeft() != null)
	{
		int left[len-1];
		getLeftElemsOfVal(left, nums, val);
		return isOnSamePath(left, root->getLeft());
	}
	else
	{
		return true;
	}
	if(val == smallest && root->getRight() != null)
	{
		int right[len-1];
		getRightElemsOfVal(right, nums, val);
		return isOnSamePath(right, root->getRight());
	}
	else
	{	
		return true;
	}
	
	
}

1. Sort the array => g_sorted.
Repeat the following until (!g_sorted.empty() || current_node != NULL)
{
2. if max(g_sorted) > current_node.val && min(g_sorted) < current_node.val => return false;
3. if max(g_sorted) < current_node.val => go left;
3. if min(g_sorted) > current_node.val => go right;
4. if max(g_sorted) == current_node.val => remove max(g_sorted) from the array, go to Step 2.
5. if min(g_sorted) == current_node.val => remove min(g_sorted) from the array, go to Step 2.
}

if(!g_sorted.empty()) return false

Algo :
1) Use hash to check if the current node is in the array.
2) Take a boolean array which will be used to keep track of found elemets.
3) Global count variable to keep track of number of elements found.
4) Do an in-order traversal :
5) for each node check if the element is part of array in the hash if yes then mark that element as found in boolean array and increase the count.
6) While returning back from that recursion reset the value in the boolean array and decrease the count variable.
7) When count is equal to length of the array it says that we found the path.
Space : O(number of elements in the array) -> Hash and boolean hash/array
Time : O(number of nodes in the tree)

This approach was easiest to visualize for me. Assumes large tree and small targetList. If targetList is very large, may be more efficient to remove the IsLargestItem and IsSmallestItem checks.

Basically, you recurse down left and right sides of tree, removing items from targetlist as you encounter them. If list on either side is empty, that means there exists a path that contains all items in targetList.

public static bool CheckForPath(Node root, List<int> targetList)
        {
            if (root == null || targetList.Count == 0) return false;

            // handle case where tree contains only root that is in targetList
            if (targetList.Contains(root.Data))
            {
                targetList.Remove(root.Data);
                if (targetList.Count == 0) 
                    return true;
            }

            // clone lists for left and right sides of tree
            var leftList = targetList.ToList();
            var rightList = targetList.ToList();

            CheckForPathHelper(root.Left, leftList);
            CheckForPathHelper(root.Right, rightList);

            // if we found a valid path on either side, that side's list will have zero elements
            return leftList.Count == 0 || rightList.Count == 0;
        }

        public static void CheckForPathHelper(Node current, List<int> targetList)
        {
            if (current == null) return;

            if (targetList.Contains(current.Data))
            {
                // current node is in G, so remove from G
                targetList.Remove(current.Data);
            }

            if (targetList.Count > 0)
            {
                // recurse left if there's still smaller items in G
                if (current.Left != null && !IsSmallestItem(targetList, current.Data))
                    CheckForPathHelper(current.Left, targetList);

                // recurse right if there's still larger items in G
                if (current.Right != null && !IsLargestItem(targetList, current.Data))
                    CheckForPathHelper(current.Right, targetList);
            }
        }

        private static bool IsLargestItem(List<int> list, int i)
        {
            return list.Max(x => x) == i;
        }
        private static bool IsSmallestItem(List<int> list, int i)
        {
            return list.Min(x => x) == i;
        }

Sort your g array.
Create a boolean array, say "test" of same size as g, set all to false.

Have a binary_search routing that returns the index of match in g, or -1 on failure.

check(Tree T)
{
flag_already_set = false;
if(! T )
{
//end of a path, add your check of "test" for all true here
return;
}
//at a node: binary search the data in g array, set flag if found
if( (ret = binary_search(g, T->data) ) != -1 )
{
if( g[ret] == true ) flag_already_set = true;
else g[ret] == true;
}
check(T->left);
check(T->right);
if(ret != -1 && flag_already_set == false)
g[ret]=false; // this node set the flag, so must unwind it
}

sort the vector array in increasing order
and then call
steps
1) sort the input array g
2) if root <= min then find if same path in root->right
3) if root >= max then find if same path in root->left
4) if min<root<max then not same path

bool ifsamepath(BinaryTree * root,vector<int> b,int length)
{
	if(root == NULL && length!=0)
		return false;
	if(length==0)
		return true;
	if(root->data == b[0])
	{
		b.erase(b.begin());
		return ifsamepath(root->right,b,length-1);
	}
	else if(root->data == b[length-1])
	{
		b.erase(b.end());
		return ifsamepath(root->left,b,length-1);
	}
	else
	{
		if(root->data > b[length-1])
		return ifsamepath(root->left,b,length);
		else if(root->data < b[0])
		return ifsamepath(root->right,b,length);
		else
		{
			return false;
		}
	}
}

This problem may be solved without sorting.
Let's call the size of group 'g' G(n) and size of BST as N.

Step 1) Time : O( G(n) )
Find the max and minimum element in the group 'g'.

Step 2) Time : O( log(N) )
Search for min and max elements of group g (Previously calculated) in the BST. Verify if these have the same path, if they do, all the intermediate elements will also have the same path.

My solution is
augment the BST, for each node in the Tree save 2 flags: left_child_visited right_child_visited
For each element in the array, search it in BST, and update the flags
Within the search, if we met a node with both flags as TRUE, then return : NOT in a single path.

At the end of the search, return: in a single path.

For size of BST = N, size of Array = n,
time complexity is O(n * log N)

1.Sort the elements to be searched to be stored in arr[]
2.Now Start from the root of bst.
2.1 search root element in the array arr

if it's index is index>0 or (index < arr.length -1) return false

else if index is 0 then move to Tree's right and arr is from 1 to arr.length-1


or if index is arr.length-1 move to tree's left and arr is now from 0 to arr.length-2;

at the end arr should be empty.

return true

1. sort the elements in g.
2. traverse the tree in in-order. Since in-order traverses each node from smallest to the biggest in ascending order, both g, the each node in in-order traverse should be the same.

so
int g[] = { 2,3,4,3,1,0}
quicksort( g );

and call inorder( node);

bool inorder( node* hd)
{
static int n = 0;
if ( hd->left) inorder( hd->left);
if (g[n++] != hd->data)
return false ;
if ( hd->right) inorder( hd_>right);
}

quicksort