Count of nodes which are at a distance X from root and leaves

0 0 9 minutes read

Given two integers N and X, where N is the number of nodes in an almost complete binary tree. The task is to find:

The number of nodes that are at X distance from the root.
The number of nodes that are at X distance from any leaf in its subtree.

Note: A Complete binary tree is a binary tree in which every level, except possibly the last, is completely filled and all nodes are as far left as possible.

Examples:

Input: N = 6, X = 0
Output: 
1
3
Complete Binary Tree of 6 nodes is
         1
       /    \  
      2      3 
    /  \    / 
   4    5  6
Nodes that are at 0 distance from root = 1 (root itself).
Nodes that are at 0 distance from any of the leaf = 3 (all the leaves of the tree)

Input: N = 13, X = 1
Output:
2
4
Complete Binary Tree of 13 nodes.
                       1
                  /         \  
                2             3 
              /   \         /   \
            4      5       6     7
          /  \    /  \   /  \  
         8    9  10  11 12  13
Nodes that are at 0 distance from root = 2 (node no. 2 and 3)
Nodes that are at 0 distance from any of the leaf = 4 (node no. 4, 5, 6 and 3)

Approach:

Finding the number of nodes that are x distance away from the root is simple. We simply print the number of nodes at x-th height. We know that in a complete binary tree every level is complete, except possibly the last and all nodes are as far left as possible. So, the height h of a complete binary tree is calculated as floor(log2(n)) where n is the total number of nodes. Also, the number of nodes at i-th height will be 2ⁱ and the number of nodes that are at last level (i.e at height h) = 2^h – (max_total_nodes – n), where 2^h are maximum nodes at height h.
Finding the number of nodes that are x distance away from any leaf in its subtree is a little bit tricky. It’s about observing the fact that if we have l leaf nodes then, ceil(l/2) nodes are 1 unit distance away from leaves, ceil(l/4) nodes are 2 units distance away from leaves …. till ceil(l/2ⁱ) nodes are i units distance away from leaves. We will first find the count of leaf nodes and apply the above method to find nodes that are x distance away from leaf.

Below is the implementation of the above approach:

C++

// C++ implementation of the approach
#include <bits/stdc++.h>
using namespace std;
 
// Function to find the count
// of the required nodes
void countNodes(int N, int X)
{
 
    // Height of the complete binary
    // tree with n nodes
    int height = floor(log2(N));
 
    // If X > height then no node
    // can be present at that level
    if (X > height) {
        cout << "0\n0";
        return;
    }
 
    // Corner case
    if (N == 1) {
        cout << "1\n1";
        return;
    }
 
    // Maximum total nodes that are possible
    // in complete binary tree with height h
    int max_total_nodes = (1 << (height + 1)) - 1;
 
    // Nodes at the last level
    int nodes_last_level
        = (1 << height) - (max_total_nodes - N);
 
    // To store the count of nodes
    // x dist away from root
    int from_root;
 
    // To store the count of nodes
    // x dist away from leaf
    int from_leaf;
 
    // If X = h then print nodes at last level
    // else nodes at Xth level
    if (X == height)
        from_root = nodes_last_level;
 
    // 2^X
    else
        from_root = 1 << X;
 
    // Number of left leaf nodes at (h-1)th level
    // observe that if nodes are not present at last level
    // then there are a/2 leaf nodes at (h-1)th level
    int left_leaf_nodes
        = ((1 << height) - nodes_last_level) / 2;
 
    // If X = h then print leaf nodes at the last h level
    // + leaf nodes at (h-1)th level
    if (X == 0) {
        from_leaf = nodes_last_level + left_leaf_nodes;
    }
    else {
 
        // First calculate nodes for leaves present at
        // height h
        int i = X;
 
        while (nodes_last_level > 1 && i > 0) {
            nodes_last_level
                = ceil((float)nodes_last_level / (float)2);
            i--;
        }
 
        from_leaf = nodes_last_level;
 
        // Then calculate nodes for leaves present at height
        // h-1
        i = X;
        while (left_leaf_nodes > 1 && i > 0) {
            left_leaf_nodes
                = ceil((float)left_leaf_nodes / (float)2);
            i--;
        }
 
        // Add both the results
        from_leaf += left_leaf_nodes;
    }
 
    cout << from_root << endl << from_leaf;
}
 
// Driver code
int main()
{
    int N = 38, X = 3;
 
    countNodes(N, X);
 
    return 0;
}

Java

// Java implementation of the approach
import java.util.*;
 
class GFG {
 
    // Function to find the count
    // of the required nodes
    static void countNodes(int N, int X)
    {
 
        // Height of the complete binary
        // tree with n nodes
        int height
            = (int)Math.floor(Math.log(N) / Math.log(2));
 
        // If X > height then no node
        // can be present at that level
        if (X > height) {
            System.out.println("0\n0");
            return;
        }
 
        // Corner case
        if (N == 1) {
            System.out.println("1\n1");
            return;
        }
 
        // Maximum total nodes that are possible
        // in complete binary tree with height h
        int max_total_nodes = (1 << (height + 1)) - 1;
 
        // Nodes at the last level
        int nodes_last_level
            = (1 << height) - (max_total_nodes - N);
 
        // To store the count of nodes
        // x dist away from root
        int from_root;
 
        // To store the count of nodes
        // x dist away from leaf
        int from_leaf;
 
        // If X = h then print nodes at last level
        // else nodes at Xth level
        if (X == height)
            from_root = nodes_last_level;
 
        // 2^X
        else
            from_root = 1 << X;
 
        // Number of left leaf nodes at (h-1)th level
        // observe that if nodes are not present at last
        // level then there are a/2 leaf nodes at (h-1)th
        // level
        int left_leaf_nodes
            = ((1 << height) - nodes_last_level) / 2;
 
        // If X = h then print leaf nodes at the last h
        // level
        // + leaf nodes at (h-1)th level
        if (X == 0) {
            from_leaf = nodes_last_level + left_leaf_nodes;
        }
        else {
 
            // First calculate nodes for leaves present at
            // height h
            int i = X;
 
            while (nodes_last_level > 1 && i > 0) {
                nodes_last_level = (int)Math.ceil(
                    (float)nodes_last_level / (float)2);
                i--;
            }
 
            from_leaf = nodes_last_level;
 
            // Then calculate nodes for leaves present at
            // height h-1
            i = X;
            while (left_leaf_nodes > 1 && i > 0) {
                left_leaf_nodes = (int)Math.ceil(
                    (float)left_leaf_nodes / (float)2);
                i--;
            }
 
            // Add both the results
            from_leaf += left_leaf_nodes;
        }
 
        System.out.println(from_root + "\n" + from_leaf);
    }
 
    // Driver Code
    public static void main(String[] args)
    {
        int N = 38, X = 3;
        countNodes(N, X);
    }
}
 
// This code is contributed by
// sanjeev2552

Python3

# Python3 implementation of the approach
from math import log2, ceil, floor
 
# Function to find the count
# of the required nodes
def countNodes(N, X):
 
    # Height of the complete binary
    # tree with n nodes
    height = floor(log2(N))
 
    # If X > height then no node
    # can be present at that level
    if (X > height):
        print("0\n0")
        return
 
    # Corner case
    if (N == 1):
        print("1\n1")
        return
 
    # Maximum total nodes that are possible
    # in complete binary tree with height h
    max_total_nodes = (1 << (height + 1)) - 1
 
    # Nodes at the last level
    nodes_last_level = (1 << height) - (max_total_nodes - N)
 
    # To store the count of nodes
    # x dist away from root
    from_root = 0
 
    # To store the count of nodes
    # x dist away from leaf
    from_leaf = 0
 
    # If X = h then print nodes at last level
    # else nodes at Xth level
    if (X == height):
        from_root = nodes_last_level
 
    # 2^X
    else:
        from_root = 1 << X
 
    # Number of left leaf nodes at (h-1)th level
    # observe that if nodes are not present at last level
    # then there are a/2 leaf nodes at (h-1)th level
    left_leaf_nodes = ((1 << height) - nodes_last_level) // 2
 
    # If X = h then print leaf nodes at the last h level
    # + leaf nodes at (h-1)th level
    if (X == 0):
        from_leaf = nodes_last_level + left_leaf_nodes
    else:
        # First calculate nodes for leaves present at
        # height h
        i = X
 
        while (nodes_last_level > 1 and i > 0):
            nodes_last_level = ceil(nodes_last_level / 2)
            i-=1
 
        from_leaf = nodes_last_level
 
        # Then calculate nodes for leaves present at height
        # h-1
        i = X
        while (left_leaf_nodes > 1 and i > 0):
            left_leaf_nodes = ceil(left_leaf_nodes / 2)
            i -= 1
 
        # Add both the results
        from_leaf += left_leaf_nodes
 
    print(from_root)
    print(from_leaf)
 
# Driver code
if __name__ == '__main__':
    N, X = 38, 3
 
    countNodes(N, X)
 
    # This code is contributed by mohit kumar 29.

C#

// C# implementation of the approach
using System;
 
class GFG{
 
// Function to find the count
// of the required nodes
static void countNodes(int N, int X)
{
     
    // Height of the complete binary
    // tree with n nodes
    int height = (int)Math.Floor(Math.Log(N) / 
                                 Math.Log(2));
 
    // If X > height then no node
    // can be present at that level
    if (X > height)
    {
        Console.Write("0\n0");
        return;
    }
 
    // Corner case
    if (N == 1)
    {
        Console.Write("1\n1");
        return;
    }
 
    // Maximum total nodes that are possible
    // in complete binary tree with height h
    int max_total_nodes = (1 << (height + 1)) - 1;
 
    // Nodes at the last level
    int nodes_last_level = (1 << height) - 
                           (max_total_nodes - N);
 
    // To store the count of nodes
    // x dist away from root
    int from_root;
 
    // To store the count of nodes
    // x dist away from leaf
    int from_leaf;
 
    // If X = h then print nodes at last level
    // else nodes at Xth level
    if (X == height)
        from_root = nodes_last_level;
 
    // 2^X
    else
        from_root = 1 << X;
 
    // Number of left leaf nodes at (h-1)th level
    // observe that if nodes are not present at last
    // level then there are a/2 leaf nodes at (h-1)th
    // level
    int left_leaf_nodes = ((1 << height) - 
                           nodes_last_level) / 2;
 
    // If X = h then print leaf nodes at the last h
    // level
    // + leaf nodes at (h-1)th level
    if (X == 0)
    {
        from_leaf = nodes_last_level + 
                    left_leaf_nodes;
    }
    else
    {
         
        // First calculate nodes for leaves present
        // at height h
        int i = X;
 
        while (nodes_last_level > 1 && i > 0)
        {
            nodes_last_level = (int)Math.Ceiling(
                (float)nodes_last_level / (float)2);
                 
            i--;
        }
 
        from_leaf = nodes_last_level;
 
        // Then calculate nodes for leaves present at
        // height h-1
        i = X;
        while (left_leaf_nodes > 1 && i > 0) 
        {
            left_leaf_nodes = (int)Math.Ceiling(
                (float)left_leaf_nodes / (float)2);
                 
            i--;
        }
 
        // Add both the results
        from_leaf += left_leaf_nodes;
    }
 
    Console.Write(from_root + "\n" + from_leaf);
}
 
// Driver Code
public static void Main()
{
    int N = 38, X = 3;
    countNodes(N, X);
}
}
 
// This code is contributed by subham348

Javascript

<script>
 
// Javascript implementation of the approach
 
// Function to find the count
// of the required nodes
function countNodes(N, X)
{
     
    // Height of the complete binary
    // tree with n nodes
    let height = Math.floor(Math.log(N) /
                            Math.log(2));
 
    // If X > height then no node
    // can be present at that level
    if (X > height) 
    {
        document.write("0<br>0");
        return;
    }
 
    // Corner case
    if (N == 1) 
    {
        document.write("1<br>1");
        return;
    }
 
    // Maximum total nodes that are possible
    // in complete binary tree with height h
    let max_total_nodes = (1 << (height + 1)) - 1;
 
    // Nodes at the last level
    let nodes_last_level = (1 << height) - 
                           (max_total_nodes - N);
 
    // To store the count of nodes
    // x dist away from root
    let from_root;
 
    // To store the count of nodes
    // x dist away from leaf
    let from_leaf;
 
    // If X = h then print nodes at last level
    // else nodes at Xth level
    if (X == height)
        from_root = nodes_last_level;
 
    // 2^X
    else
        from_root = 1 << X;
 
    // Number of left leaf nodes at (h-1)th level
    // observe that if nodes are not present at last
    // level then there are a/2 leaf nodes at (h-1)th
    // level
    let left_leaf_nodes = Math.floor(
        ((1 << height) - nodes_last_level) / 2);
 
    // If X = h then print leaf nodes at the last h
    // level
    // + leaf nodes at (h-1)th level
    if (X == 0)
    {
        from_leaf = nodes_last_level + 
                    left_leaf_nodes;
    }
    else
    {
         
        // First calculate nodes for leaves
        // present at height h
        let i = X;
 
        while (nodes_last_level > 1 && i > 0) 
        {
            nodes_last_level = Math.floor(Math.ceil(
                nodes_last_level / 2));
            i--;
        }
 
        from_leaf = nodes_last_level;
 
        // Then calculate nodes for leaves present at
        // height h-1
        i = X;
        while (left_leaf_nodes > 1 && i > 0) 
        {
            left_leaf_nodes = Math.floor(Math.ceil(
                left_leaf_nodes / 2));
            i--;
        }
 
        // Add both the results
        from_leaf += left_leaf_nodes;
    }
    document.write(from_root + "<br>" + from_leaf);
}
 
// Driver Code
let N = 38, X = 3;
countNodes(N, X);
 
// This code is contributed by unknown2108
 
</script>

Output:

8
3

Time Complexity: O(log (N) )

Auxiliary Space: O(1), since no extra space has been taken.

Feeling lost in the world of random DSA topics, wasting time without progress? It’s time for a change! Join our DSA course, where we’ll guide you on an exciting journey to master DSA efficiently and on schedule.
Ready to dive in? Explore our Free Demo Content and join our DSA course, trusted by over 100,000 zambiatek!