CareerCup

it can be done with a modified post-order traverse. To simplify things, i'll put it in recursive style:

int pot(BinaryTree *p) {
	int count = 0;
	if (!p) return count;
	count += pot(p->left);
	count += pot(p->right);
	if (count == k) cout<<&p<<endl;
	return count;
}

Complexity O(n)

public List getListOfNodes(Node root,int k)
{
  ArrayList<Node> list= new ArrayList<Node>()
  getLeaves(root,list,k);
  return list;
}

public int getLeaves(Node node,ListnNode[] nodeList,int  k)
{
  int numLeafL,numLeafR=0
  if(node.getLeft==null && node.getRight==null)
  {
    return 1;
  }
  if(node.getLeft)
  {
  numleafL=getLeaves(node.getLeft);
  
  }
  if(node.getRight)
  {
  numleafR=getLeaves(node.getRight);
   }
   
   
   currentLeafcount=numLeafL+numRight;
   if(currentLeafCount==k)
   {
   nodeList.add(node)
   }
   return currenLeafCount;
   
   
}

We have to use Bottom up approach
1. Traverse the tree in postorder manner.
2.While traversing keep count of the leaf nodes
3. add nodes who have k leaves to list
4. At the end LIst will contain the ans

int getNodeWithKLeaves(Node root,int k,LinkedList<Integer> list)
   {
       if(root==null)
           return 0;
       int x=0;
       x+=getNodeWithKLeaves(root.left, k, list);
       x+=getNodeWithKLeaves(root.right, k, list);
       
       if(root.left==null&&root.right==null)
           x++;
       if(k==x)
           list.add(root.info);
       return x;
   }

Have a recursive method called getNoOfLeaves(). The base case of recursion returns 1 for leaf nodes. During the bubbling up(unwinding) of the recursive calls, sum up the number of leaves from both it's children and check if it equals to the given k. If yes, add the node to a list.

Complexity O(n)

public int findNodesWithK(Node node ,int k, LinkedList<Node> list){
    	if (node==null){
    		return 0;
    	}else{
    		int count = findNodesWithK(node.left,k,list) + findNodesWithK(node.right,k,list);
    		if (count==k){
    			list.add(node);
    		}
    		return count+1 ;
    	}

}

int CountLeafeNodes(Node* root)
	{
		if(root==NULL)return 0;
		if(root->left==NULL&&root->right==NULL)return 1;
		return CountLeafeNodes(root->left)+CountLeafeNodes(root->right);
	}