CareerCup

In fact, as a node, I am a leaf i.i.f. the node following me in the preorder traversal array is greater than the first of my ancestors which is greater than me. So while traversing the BST, we need to maintain the stack of the ancestors that are greater than the current node.

In java, something like:

public static List<Integer> getLeaves(List<Integer> bst) {
        List<Integer> leaves = new ArrayList<>();
        
        Stack<Integer> greaterAncestors = new Stack<>();

        int previous = 0;

        for (int i: bst) {
            int ancestor = 0;
            // Find the first ancestor which is greater than the current node.
            while (!greaterAncestors.isEmpty() && greaterAncesters.peek() < i) {
                ancestor = greaterAncestors.pop();
            }
            greaterAncestors.push(i);
            if (ancestor > previous) {
                leaves.add(previous);
            }
            previous = i;
        }

        if (!bst.isEmpty()) {
            // The last node is always a leaf.
            leaves.add(previous);
        }

        return leaves;
    }

public static void findLeafs(int[] arr) {
		if (arr == null || arr.length == 0)
			return;

		Stack<Integer> stack = new Stack<>();
		for(int n = 1, c = 0; n < arr.length; n++, c++) {
			if (arr[c] > arr[n]) {
				stack.push(arr[c]);
			} else {
				boolean found = false;
				while(!stack.isEmpty()) {
					
					if (arr[n] > stack.peek()) {
						stack.pop();
						found = true;
					} else 
						break;		
				}
				if (found) 
					System.out.println(arr[c]);	
			}

		}
		System.out.println(arr[arr.length-1]);
	}

Two things to remember:
- In case of preorder, when we see a number increasing in order, then the smaller number is a leaf node
- Last element in the array is ALWAYS a leaf node

public void printLeafNodes(int[] arr) {
	if (arr == null || arr.length == 0)
		return;

	int prev = arr[0];
	for (int i = 1; i < arr.length; i++) {
		if (prev < arr[i]) {
			System.out.println(prev);
		}

		prev = arr[i];
	}

	// Always print last element
	System.out.println(prev);
}

public static void FindLeafNodes(int[] a, int low, int high){
       if(a.length==0 || low>high)
           return;
        else if(low==high || low==high-1){
            System.out.println(a[high]);
            return;
        }
        else{
            int j= low+1;
            while(j<=high && a[j]<a[low] )
                j++;
            FindLeafNodes(a,low+1,j-1);
            FindLeafNodes(a,j,high);
            
        }
    }

{
  private static List<Integer> listLeaves(int[] arr, int start, int end) {
    List<Integer> retList = new ArrayList<>();
    if (start == end) {
      retList.add(arr[start]);
    } else {
      int pos = start + 1;
      for (; arr[pos] < arr[start]; pos++) ;
      retList.addAll(listLeaves(arr, start + 1, pos - 1));
      retList.addAll(listLeaves(arr, pos, end));
    }
    return retList;
  }

This is like finding if increase or decrease. For preorder traversal, we can find leaf if there is decrease (prev) and increase (current).

public void findLeafNodes(int[] nodes) {
			boolean prevDecrease = false;
			boolean currentIncrease = false;

			int prevValue = nodes[0];
			for(int i=1; i< nodes.length; i++) {
				if(prevValue > nodes[i]) {
					prevDecrease = true;
					currentIncrease = false;
				}
				else
					currentIncrease = true;
				
				if(prevDecrease && currentIncrease) {
					System.out.print(prevValue + " " + nodes[i] +" ");
					prevDecrease = false;				
				}

				prevValue = nodes[i];
			}
		}

Call printLeavesFromPreorder(arr, 0, arr.Length-1)

public static void printLeavesFromPreorder(int[] arr, int low, int high)
        {
            if(arr == null || arr.Length == 0)
            {
                return;
            }
            // find where left subtree ends
            int left = findLeftSubtreeEnd(arr, low, high);
            // find where right subtree starts
            int right = low+1;
            if (left != -1)
            {
                right = left + 1;
            }
            if(left == -1 && right >= high)
            {
                Console.WriteLine(arr[low]);
            } else
            {
                // search in left subtree
                printLeavesFromPreorder(arr, low + 1, left);
                // search in right subtree
                printLeavesFromPreorder(arr, right, high);
            }
        }

        private static int findLeftSubtreeEnd(int[] arr, int thisindex, int end)
        {
            int result = thisindex + 1;
            if(result >= end)
            {
                return -1; // no left subtree
            }
            while(result < end && arr[result] < arr[thisindex])
            {
                result++;
            }
            result--;
            return result;
        }

We need to keep track of all non-leaf nodes to to detect the leaf nodes which are the right child of their parents

public List<int> FindLeafNodes(int[] nums)
       {
           var result = new List<int>();
           if (nums.Length == 1) { result.Add(nums[0]); return result; }

           var parents = new List<int>();
           for (int i = 0; i < nums.Length-1; i++)
           {
               if (nums[i + 1] <= nums[i]) { parents.Add(nums[i]); continue; } // nodes with left child
               else {
                   if (OnSameSide(nums[i], nums[i + 1], parents)) { parents.Add(nums[i]); continue; } // node with right child
                   else {
                       result.Add(nums[i]);
                   }
               }
           }

           result.Add(nums[nums.Length - 1]);

           return result;
       }

       bool OnSameSide(int a, int b, List<int> parents)
       {
           for (int i = parents.Count - 1; i >= 0; i--)
           {
               if (a < parents[i] && b > parents[i]) return false;
           }
           
           return true;	
       }

public List<int> FindLeafNodes(int[] nums)
       {
           var result = new List<int>();
           if (nums.Length == 1) { result.Add(nums[0]); return result; }

           var parents = new List<int>();
           for (int i = 0; i < nums.Length-1; i++)
           {
               if (nums[i + 1] <= nums[i]) { parents.Add(nums[i]); continue; } // nodes with left child
               else {
                   if (OnSameSide(nums[i], nums[i + 1], parents)) { parents.Add(nums[i]); continue; } // node with right child
                   else {
                       result.Add(nums[i]);
                   }
               }
           }

           result.Add(nums[nums.Length - 1]);

           return result;
       }

       bool OnSameSide(int a, int b, List<int> parents)
       {
           for (int i = parents.Count - 1; i >= 0; i--)
           {
               if (a < parents[i] && b > parents[i]) return false;
           }
           
           return true;
       }

@Benc Good Work!

public static void FindLeafNodes(int[] a, int low, int high){
       if(a.length==0 || low>high)
           return;
        else if(low==high || low==high-1){
            System.out.println(a[high]);
            return;
        }
        else{
            int j= low+1;
            while(j<=high && a[j]<a[low] )
                j++;
            FindLeafNodes(a,low+1,j-1);
            FindLeafNodes(a,j,high);
            
        }
    }

public static void FindLeafNodes(int[] a, int low, int high){
       if(a.length==0 || low>high)
           return;
        else if(low==high || low==high-1){
            System.out.println(a[high]);
            return;
        }
        else{
            int j= low+1;
            while(j<=high && a[j]<a[low] )
                j++;
            FindLeafNodes(a,low+1,j-1);
            FindLeafNodes(a,j,high);
            
        }
    }

public static void FindLeafNodes(int[] a, int low, int high){
       if(a.length==0 || low>high)
           return;
        else if(low==high || low==high-1){
            System.out.println(a[high]);
            return;
        }
        else{
            int j= low+1;
            while(j<=high && a[j]<a[low] )
                j++;
            FindLeafNodes(a,low+1,j-1);
            FindLeafNodes(a,j,high);
            
        }
    }

public static void FindLeafNodes(int[] a, int low, int high)
    {
       if(a.length==0 || low>high)
           return;
        else if(low==high || low==high-1)
       {
            System.out.println(a[high]);
            return;
       }
        else
       {
            int j= low+1;
            while(j<=high && a[j]<a[low] )
                j++;
            FindLeafNodes(a,low+1,j-1);
            FindLeafNodes(a,j,high);
            
       }
    }

Here is my version, we need to maintain invariant where if we have two elements in stack less than current element at least then we need to store first less element to result as it will be leaf. At the end, to cover the last element we need to store the top element from stack (this covers the case of only one element as well).

vector<int>
preorder_find_leaf(const vector<int> &array) {
    if (!array.size()) {
        return {};
    }
    stack<int> pstack;
    vector<int> result;
    for (int i = 0; i < array.size(); i++) {
        if (!pstack.empty() && pstack.top() < array[i]) {
            int prev = pstack.top();
            pstack.pop();
            bool twoless = false;
            while (!pstack.empty() && pstack.top() < array[i]) {
                twoless = true;
                pstack.pop();
            }

            if (twoless) {
                result.push_back(prev);
            }
        }
        pstack.push(array[i]);
    }

    if (!pstack.empty()) {
        result.push_back(pstack.top());
    }

    return result;
}

int extract_leaves(vector<int> &prefix, int pos, int subtree_max, vector<int> &leaves) {
if (pos >= prefix.size() || prefix[pos] > subtree_max)
return pos;
int root = prefix[pos++];
int pos1 = extract_leaves(prefix, pos, min(subtree_max, root), leaves);
int pos2 = extract_leaves(prefix, pos1, subtree_max, leaves);
if (pos2 == pos)
leaves.push_back(root);
return pos2;
}

You can solve it in O(n) time and O(n) space by using the BST property.

static Stack<Range> stack = new Stack<>();

static class Range{
int min;
int max;

Range(int min, int max){
this.min = min;
this.max = max;
}
}
public static List<Integer> findLeaves(int[] pre){
List<Integer> leaves = new ArrayList<>();

if(pre == null || pre.length == 0)
return leaves;


stack.push(new Range(Integer.MIN_VALUE, Integer.MAX_VALUE));

for(int i=0; i<pre.length; i++){
Range curr = stack.pop();

//confirm in the range
if(curr.min < pre[i] && pre[i] < curr.max){
pushRightLeftToStack(curr, pre[i]);
}
else{
Range next = stack.pop();
if(next.min < pre[i] && pre[i] < next.max){
pushRightLeftToStack(next, pre[i]);
}
else{
leaves.add(next.min); //dont forget to add this leaf
leaves.add(pre[i]);
}
}
}

return leaves;
}

private static void pushRightLeftToStack(Range r, int val){
Range right = new Range(val, r.max);
Range left = new Range(r.min, val);
stack.push(right);
stack.push(left);
}

With recursion, First node is parent, First recursion is in all nodes less that or equal that parent; second recursion is on all nodes greather that parent

public static IEnumerable<int> FindNodes(int[] a)
{
	if (a == null || a.Length == 0)
		return Array.Empty<int>();
	
	var nodes = new List<int>();
	FindNodes(a, 0, a.Length -1, nodes);
	return nodes;
}

private static void FindNodes(int[] a, int begin, int end, List<int> nodes)
{
	if (begin == end)
	{
		nodes.Add(a[begin]);
		return;
	}
	
	if (end < begin)
		return;
	
	int parent = a[begin];
	// Skip the parent
	begin++;
	int i = begin;
	while (i <= end && a[i] <= parent)
		i++;
	
	FindNodes(a, begin, i - 1, nodes);
	FindNodes(a, i, end, nodes);
}

Swift Version:::

func getLeafNodes(_ a: [Int]) -> [Int]? {
    var arr = a
    guard arr.count > 1 else {
        return a
    }
    let firstElement = arr.first!
    var i = 1
    while i < arr.count && arr[i] < firstElement {
        i += 1
    }
    arr.removeFirst()
    arr.insert(firstElement, at: i-1)
    
    let left = getLeafNodes(Array(arr[0..<i-1]))
    let right = getLeafNodes(Array(arr[i..<arr.count]))
    
    if let l = left, let r = right {
        return l + r
    }
    
    if let l = left {
        return l
    }
    
    if let r = right {
        return r
    }
    
    return nil
}

getLeafNodes([5,3,2,4,8,7,9]) // Ans (2,4,7,9)

int size = preorder.size();
        vector<int> path;
        vector<int> leaves;
        for(int i = 0; i < size; ++i){
            if(path.size()==0 || path.back() > preorder[i]) path.push_back(preorder[i]);
            else {
		if(path.size() > 1 && preorder[i] > path[path.size()-2]) leaves.push_back(path[path.size()-1);
                while(path.size()>=0 && path.back() < preorder[i]){
                    path.pop_back();
                }
                path.push_back(preorder[i]);
            }
        }
        return leaves;

private static List<Integer> listLeaves(int[] arr, int start, int end) {
List<Integer> retList = new ArrayList<>();
if (start == end) {
retList.add(arr[start]);
} else {
int pos = start + 1;
for (; arr[pos] < arr[start]; pos++) ;
retList.addAll(listLeaves(arr, start + 1, pos - 1));
retList.addAll(listLeaves(arr, pos, end));
}
return retList;
}

// JS
function identifyLeavesFromPreOrder(nums) {
  let leaves = [];

  // we're at the leaves when sub-tree has only 1 value
  if (nums.length === 1) {
    leaves = leaves.concat(nums);
  }
  else if (nums.length > 1) {
    // root has to be the first in PreOrder.
    const root = nums[0];

    // children are next-largest and next-smallest numbers.
    const sortedNums = nums.slice().sort((a, b) => a < b ? -1 : 1); // small to large
    const rootInd = sortedNums.indexOf(root);
    const rightChildInd = rootInd + 1;

    // sub-trees from children down.
    // (will be empty if children are missing.)
    const leftNums = nums.slice(1, rightChildInd); // up to but not including
    const rightNums = nums.slice(rightChildInd);   // to end

    leaves = leaves.concat(identifyLeavesFromPreOrder(leftNums));
    leaves = leaves.concat(identifyLeavesFromPreOrder(rightNums));
  }

  return leaves;
}

@BenC, if you have preorder of 5 4 2 1 3, both 1 and 3 are leaves, but only 3 gets printed in your algorithm?

Need to traverse through the array and everytime we find a number greater than previous value, that previous value is a leaf node.
Also, last element is ALWAYS a leaf node

public void printLeafNodes(int[] arr) {
	if (arr == null || arr.length == 0)
		return;

	int prev = arr[0];
	for (int i = 1; i < arr.length; i++) {
		if (prev < arr[i]) {
			System.out.println(prev);
		}

		prev = arr[i];
	}

	// Always print last element
	System.out.println(prev);
}

#include <stdlib.h>
#include <stdio.h>

static int t1[] = {5,3,2,4,8,7,9};
static int nt1 = 7;

void
leaves(int* t, int* et)
{
	int *u;

	if(t >= et)
		return;
	if(et-t == 1){
		printf("%d ", *t);	/* the leaf */
		return;
	}
	u = t+1;
	while(u<et && *u<*t)
		u++;
	leaves(t+1, u);	/* left sub-tree */
	leaves(u, et);	/* right sub-tree */
}

int
main(int argc, char* argv[]){
	leaves(t1, t1+nt1);
	printf("\n");
	return 0;
}

public clas Solution {
  public List<Integer> getLeaves(int[] array) {
    List<Integer> leaves = new ArrayList<>();
    if(array == null || array.length == 0) {
      return leaves;
    }
    getLeaves(array, Integer.MIN_VALUE, Integer.MAX_VALUE, leaves);
    return leaves;
  }

  private int getLeaves(int[] array, int index, int minValue, int maxValue, List<Integer> leaves) {
    if(index == array.length - 1) {
      leaves.add(array[index]);
      return index + 1;
    }

    // if the next value doesnt fall in the bucket then this node is the leaf as the next noad falls outside
    // the allowable range
    int childIndex = index + 1;
    if(array[childIndex] >= maxValue || array[childIndex] < minValue) {
      leaves.add(array[index]);
      return childIndex;
    }
    // This means that this node is not a leaf hence keep on traversing
    if(array[childIndex] <= array[index]) {
      childIndex = getLeaves(array, childIndex, minValue, array[index], leaves);
    }

    if(childIndex >= array.length || array[childIndex] >= maxValue || array[childIndex] < minValue) {
      // If we are reaching this point then it means that the current node had atleast one child so simply return
      // as this node is no longer a leaf but parent with one child
      return childIndex;
    }
    // This means that we have a right child so traverse on the right child to see if thats a leaf
    if(array[childIndex] > array[index]) {
      childIndex = getLeaves(array, childIndex, array[index], maxValue, leaves);
    }

    return index;
  }
}

void printLeaf(int *v, int size) {
        if (size <= 0)
                return;

        if (size == 1) 
                printf("%d\n", v[0]);
        else {
                int first = v[0];
                int i;

                for (i = 1; i < size; ++i)
                        if (v[i] > first)
                                break;

                printLeaf(&v[1], i - 1);
                printLeaf(&v[i], size - i);
        }
}

void GetLeaves(vector<int> const &a, vector<int> &leaves,
	int start = -1, int end = -1)
{
	if (start == -1) {
		start = 0;
		end = a.size();
		leaves.clear();
	}
	if (start < 0 ||
		end < 0 ||
		end > a.size() ||
		start >= end)
	{
		return;
	}
	if (end - start == 1) {
		leaves.push_back(a[start]);
		return;
	}
	for (int i = start + 1; i < end; ++ i) {
		if (a[i] >= a[start] ||
			i + 1 == end)
		{
			GetLeaves(a, leaves, start + 1, i);
			GetLeaves(a, leaves, i, end);
			break;
		}
	}
}

static List<Integer> LeafNodes(List<Integer> nodes) {
        return leafNodesInternal(nodes, new LinkedList<Integer>());
    }

    private static List<Integer> leafNodesInternal(List<Integer> nodes, List<Integer> leaves) {
        int posL = 1;
        int posR = 1;
        while (posR < nodes.size() && nodes.get(posR) < nodes.get(0))
            posR++;
        List<List<Integer>> LLR = new LinkedList<List<Integer>>();
        LLR.add(nodes.subList(posL, posR));
        LLR.add(nodes.subList(posR, nodes.size()));
        for (List<Integer> l : LLR) {
            switch (l.size()) {
                case 0:
                    break;
                case 1:
                    leaves.add(l.get(0));
                    break;
                default:
                    leaves = leafNodesInternal(l, leaves);
                    break;
            }
        }
        return leaves;
    }