Print all nodes in a binary tree having K leaves

http://www.geeksforgeeks.org/print-nodes-binary-tree-k-leaves/

Given a binary tree and a integer value K, the task is to find all nodes in given binary tree having K leaves in subtree rooted with them.

Here any node having K leaves means sum of leaves in left subtree and in right subtree must be equal to K. So to solve this problem we use Postorder traversal of tree. First we calculate leaves in left subtree then in right subtree and if sum is equal to K, then print current node. In each recursive call we return sum of leaves of left subtree and right subtree to it’s ancestor.

static int kLeaves(Node ptr,int k) 

{ 

    // Base Conditions : No leaves 

    if (ptr == null) 

        return 0; 

  

    // if node is leaf 

    if (ptr.left == null && ptr.right == null) 

        return 1; 

  

    // total leaves in subtree rooted with this 

    // node 

    int total = kLeaves(ptr.left, k) + kLeaves(ptr.right, k); 

  

    // Print this node if total is k 

    if (k == total) 

        System.out.print(ptr.data + " "); 

  

    return total; 

}