CareerCup

//Time Complexity : O(N) Space: O(N)
public List<Integer> leaves(int[] arr){
	if(arr == null || arr.length == 0){
		return Collections.<Integer>emptyList();
	}
	List<Integer> result = new ArrayList<Integer>();
	Stack<Integer> st = new Stack<Integer>();
	for(int i = 0; i < arr.length; i++){
		Integer l = null;
		boolean leafFound = false;
		while(!st.isEmpty() && arr[i] > st.peek()){
			if(l != null && !leafFound){
				result.add(l);
				leafFound = true;
			}
			l = st.pop();
		}
		st.push(arr[i]);
		
	}
	result.add(st.pop());
	return result;
}

// O(N) time, O(depth) space complexity.
#include <iostream>
#include <vector>
#include <climits>

using namespace std;


int findLeaf(const vector<int>& pre_order, int start, int break_point, vector<int>* leaves) {
  if(pre_order.size() <= start){
    return start;
  }
  int node = pre_order[start];

  if(node > break_point){
    return start;
  }

  int end_index_left = findLeaf(pre_order, start+1, node, leaves);
  int end_index_right = findLeaf(pre_order, end_index_left, break_point, leaves);

  if(end_index_left == end_index_right && end_index_left == start+1){
    leaves->push_back(node);
  }
  return end_index_right;
}

int main(int argc, char* argv[]){
  vector<int> pre_order = {6, 3, 1, 5, 4, 8, 7, 9, 10};
  vector<int> leaves;
  int break_point = INT_MAX; // there is no break point.

  int end_index = findLeaf(pre_order,0, break_point, &leaves);

  if(end_index != pre_order.size()){
    cout << "ERROR: end index: " << end_index << " != " << pre_order.size() << endl;
    return -1;
  }
  for(const int t: leaves){
    cout << t << " ";
  }
  cout << endl;
  return 0;
}

char *leafs(char *t, int min, int max)
{
	char v = *t++;
	char *s = t;
	if (min < *t && *t < v)
		t = leafs(t, min, v);
	if (v < *t && *t < max)
		t = leafs(t, v, max);
	if (s == t)
		printf("<%c>\n", v);
	return t;
}


int main()
{
	leafs("fbadcegih", 0, 255);
}

This question seems in-complete. Otherwise wouldn't the last element of the pre-order traversal be a leaf node? Am I missing anything?

If the intent was to find a leaf node in the left sub-tree then we can follow the below steps
1. The root is the first element
2. Find the first value, say max, which is greater than root in the pre-order traversal. We can use binary search for this. Now the value before the max in the pre-order traversal is a leaf node.

This is simply not a complete description of the question. The short answer is that there is no way.
Think about two trees:
4
3 nullptr

3
nullptr 4

Both of the trees have exactly the same pre-order traversal, which is 3 4, if nullptr is not taken into account.
The leaf node can be either 3 or 4 depending on the tree, whose information is lost during pre-order traversal.
If we take nullptr into account, this is a simple question. Any time we find two nullptrs after a node, we count it as a leaf. But I guess it is not what the interviewer wanted.

O(log n) time and O(1) space.

#include <vector>
#include <iostream>

using namespace std;

int Find(const vector<int>& a, int val)
{
    if (a.empty())
    {
        return -1;
    }
    int l = 0;
    int r = a.size() - 1;
    while (l <= r)
    {
        int m = (l + r) / 2;
        if (a[m] == val)
        {
            if (m == a.size() - 1 ||
                a[m + 1] > a[m])
            {
                return m;
            }
            l = m + 1;
        }
        else if (a[m] > val)
        {
            if (m == a.size() - 1 ||
                a[m + 1] < a[m])
            {
                l = m + 1;
            }
            else
            {
                r = m - 1;
            }
        }
        else
        {
            l = m + 1;
        }
    }
    return -1;
}

int main()
{
    cout << Find({5, 3, 1, 3, 6, 5, 7}, 3) << "\n";
    return 0;
}

this is a preorder sequence of a BST rooted at 6

6 4 3 5 8 7 9

leaf nodes are 3,5,7,9

if (nums[i] < nums[i+1]) leaves.push_back(nums[i]);

This observation will be true just for leaf nodes...