Tutorialspoint.dev

Count Non-Leaf nodes in a Binary Tree

Given a Binary tree, count total number of non-leaf nodes in the tree

Examples:

Input :


Output :2
Explanation
In the above tree only two nodes 1 and 2 are non-leaf nodes



We recursively traverse the given tree. While traversing, we count non-leaf nodes in left and right subtrees and add 1 to the result.

C++

// CPP program to count total number of
// non-leaf nodes in a binary tree
#include <bits/stdc++.h>
using namespace std;
  
/* A binary tree node has data, pointer to 
  left child and a pointer to right child */
struct Node {
    int data;
    struct Node* left;
    struct Node* right;
};
  
/* Helper function that allocates a new node with the
given data and NULL left and right pointers. */
struct Node* newNode(int data)
{
    struct Node* node = new Node;
    node->data = data;
    node->left = node->right = NULL;
    return (node);
}
  
/* Computes the number of non-leaf nodes in a tree. */
int countNonleaf(struct Node* root)
{
    // Base cases.
    if (root == NULL || (root->left == NULL && 
                         root->right == NULL))
        return 0;
  
    // If root is Not NULL and its one of its
    // child is also not NULL
    return 1 + countNonleaf(root->left) + 
               countNonleaf(root->right);
}
  
/* Driver program to test size function*/
int main()
{
    struct Node* root = newNode(1);
    root->left = newNode(2);
    root->right = newNode(3);
    root->left->left = newNode(4);
    root->left->right = newNode(5);
    cout << countNonleaf(root);
    return 0;
}

Java

// Java program to count total number of 
// non-leaf nodes in a binary tree 
class GfG { 
  
/* A binary tree node has data, pointer to 
left child and a pointer to right child */
static class Node { 
    int data; 
    Node left; 
    Node right; 
}
  
/* Helper function that allocates a new node with the 
given data and NULL left and right pointers. */
static Node newNode(int data) 
    Node node = new Node(); 
    node.data = data; 
    node.left = null;
    node.right = null
    return (node); 
  
/* Computes the number of non-leaf nodes in a tree. */
static int countNonleaf(Node root) 
    // Base cases. 
    if (root == null || (root.left == null && 
                        root.right == null)) 
        return 0
  
    // If root is Not NULL and its one of its 
    // child is also not NULL 
    return 1 + countNonleaf(root.left) + 
                countNonleaf(root.right); 
  
/* Driver program to test size function*/
public static void main(String[] args) 
    Node root = newNode(1); 
    root.left = newNode(2); 
    root.right = newNode(3); 
    root.left.left = newNode(4); 
    root.left.right = newNode(5); 
    System.out.println(countNonleaf(root)); 
}

Python3

# Python3 program to count total number
# of non-leaf nodes in a binary tree

# class that allocates a new node with the
#given data and None left and right pointers.
class newNode:
def __init__(self,data):
self.data = data
self.left = self.right = None

# Computes the number of non-leaf
# nodes in a tree.
def countNonleaf(root):

# Base cases.
if (root == None or (root.left == None and
root.right == None)):
return 0

# If root is Not None and its one of
# its child is also not None
return (1 + countNonleaf(root.left) +
countNonleaf(root.right))

# Driver Code
if __name__ == ‘__main__’:

root = newNode(1)
root.left = newNode(2)
root.right = newNode(3)
root.left.left = newNode(4)
root.left.right = newNode(5)
print(countNonleaf(root))

# This code is contributed by PranchalK

C#

// C# program to count total number of 
// non-leaf nodes in a binary tree
using System;
  
class GfG 
  
    /* A binary tree node has data, pointer to 
    left child and a pointer to right child */
    class Node { 
        public int data; 
        public Node left; 
        public Node right; 
    }
  
    /* Helper function that allocates a new node with the 
    given data and NULL left and right pointers. */
    static Node newNode(int data) 
    
        Node node = new Node(); 
        node.data = data; 
        node.left = null;
        node.right = null
        return (node); 
    
  
    /* Computes the number of non-leaf nodes in a tree. */
    static int countNonleaf(Node root) 
    
        // Base cases. 
        if (root == null || (root.left == null && 
                            root.right == null)) 
            return 0; 
  
        // If root is Not NULL and its one of its 
        // child is also not NULL 
        return 1 + countNonleaf(root.left) + 
                    countNonleaf(root.right); 
    
  
    /* Driver code*/
    public static void Main(String[] args) 
    
        Node root = newNode(1); 
        root.left = newNode(2); 
        root.right = newNode(3); 
        root.left.left = newNode(4); 
        root.left.right = newNode(5); 
        Console.WriteLine(countNonleaf(root)); 
    }
}
  
// This code is contributed by PrinciRaj1992


Output:

2


This article is attributed to GeeksforGeeks.org

tags:

Tree Tree

leave a comment

code

0 Comments

load comments

Subscribe to Our Newsletter