Tutorialspoint.dev

Density of Binary Tree in One Traversal

Given a Binary Tree, find density of it by doing one traversal of it.

Density of Binary Tree = Size / Height 

Examples:

Input: Root of following tree
   10
  /   
 20   30

Output: 1.5
Height of given tree = 2
Size of given tree = 3

Input: Root of following tree
     10
    /   
   20   
 /
30
Output: 1
Height of given tree = 3
Size of given tree = 3 

Density of a Binary Tree indicates, how balanced Binary Tree is. For example density of a skewed tree is minimum and that of a perfect tree is maximum.



We strongly recommend you to minimize your browser and try this yourself first.

Two traversal based approach is very simple. First find the height using one traversal, then find the size using another traversal. Finally return the ratio of two values.
To do it in one traversal, we compute size of Binary Tree while finding its height. Below is C++ implementation.

C++

//C++ program to find density of a binary tree
#include<stdio.h>
#include<stdlib.h>
  
// A binary tree node
struct Node
{
    int data;
    Node *left, *right;
};
  
// Helper function to allocates a new node
Node* newNode(int data)
{
    Node* node = new Node;
    node->data = data;
    node->left = node->right = NULL;
    return node;
}
  
// Function to compute height and
// size of a binary tree
int heighAndSize(Node* node, int &size)
{
    if (node==NULL)
        return 0;
  
    // compute height of each subtree
    int l = heighAndSize(node->left, size);
    int r = heighAndSize(node->right, size);
  
    //increase size by 1
    size++;
  
    //return larger of the two
    return (l > r) ? l + 1 : r + 1;
}
  
//function to calculate density of a binary tree
float density(Node* root)
{
    if (root == NULL)
        return 0;
  
    int size = 0; // To store size
  
    // Finds height and size
    int _height = heighAndSize(root, size);
  
    return (float)size/_height;
}
  
// Driver code to test above methods
int main()
{
    Node* root = newNode(1);
    root->left = newNode(2);
    root->right = newNode(3);
  
    printf("Density of given binary tree is %f",
           density(root));
  
    return 0;
}

Java

// Java program to find density of Binary Tree
  
// A binary tree node
class Node 
{
    int data;
    Node left, right;
  
    public Node(int data) 
    {
        this.data = data;
        left = right = null;
    }
}
  
// Class to implement pass by reference of size
class Size 
{
    // variable to calculate size of tree
    int size = 0;
}
  
class BinaryTree 
{
    Node root;
  
    // Function to compute height and
    // size of a binary tree
    int heighAndSize(Node node, Size size) 
    {
        if (node == null)
            return 0;
  
        // compute height of each subtree
        int l = heighAndSize(node.left, size);
        int r = heighAndSize(node.right, size);
  
        //increase size by 1
        size.size++;
  
        //return larger of the two
        return (l > r) ? l + 1 : r + 1;
    }
  
    //function to calculate density of a binary tree
    float density(Node root) 
    {
        Size size = new Size();
        if (root == null)
            return 0;
                 
        // Finds height and size
        int _height = heighAndSize(root, size);
  
        return (float) size.size / _height;
    }
  
    // Driver code to test above methods
    public static void main(String[] args) 
    {
        BinaryTree tree = new BinaryTree();
        tree.root = new Node(1);
        tree.root.left = new Node(2);
        tree.root.right = new Node(3);
  
        System.out.println("Density of given Binary Tree is : "
                + tree.density(tree.root));
    }
  
}
  
// This code has been contributed by Mayank Jaiswal(mayank_24)

Python3

# Python3 program to find density
# of a binary tree 
  
# A binary tree node 
# Helper function to allocates a new node
class newNode: 
    def __init__(self, data): 
        self.data = data 
        self.left = self.right = None
          
# Function to compute height and 
# size of a binary tree 
def heighAndSize(node, size): 
  
    if (node == None) :
        return 0
  
    # compute height of each subtree 
    l = heighAndSize(node.left, size) 
    r = heighAndSize(node.right, size) 
  
    #increase size by 1 
    size[0] += 1
  
    # return larger of the two 
    return l + 1 if(l > r) else r + 1
  
# function to calculate density 
# of a binary tree 
def density(root):
  
    if (root == None) :
        return 0
  
    size = [0] # To store size 
  
    # Finds height and size 
    _height = heighAndSize(root, size) 
  
    return size[0] / _height 
  
# Driver Code 
if __name__ == '__main__':
    root = newNode(1
    root.left = newNode(2
    root.right = newNode(3
  
    print("Density of given binary tree is ",
                               density(root))
  
# This code is contributed 
# by SHUBHAMSINGH10

C#

// C# program to find density 
// of Binary Tree 
using System;
  
// A binary tree node 
class Node 
    public int data; 
    public Node left, right; 
  
    public Node(int data) 
    
        this.data = data; 
        left = right = null
    
  
// Class to implement pass
// by reference of size 
class Size 
    // variable to calculate
    // size of tree 
    public int size = 0; 
  
class BinaryTree 
Node root; 
  
// Function to compute height 
// and size of a binary tree 
int heighAndSize(Node node,
                 Size size) 
    if (node == null
        return 0; 
  
    // compute height of each subtree 
    int l = heighAndSize(node.left, size); 
    int r = heighAndSize(node.right, size); 
  
    //increase size by 1 
    size.size++; 
  
    //return larger of the two 
    return (l > r) ? l + 1 : r + 1; 
  
// function to calculate density
// of a binary tree 
float density(Node root) 
    Size size = new Size(); 
    if (root == null
        return 0; 
              
    // Finds height and size 
    int _height = heighAndSize(root, size); 
  
    return (float) size.size / _height; 
  
// Driver code 
static public void Main(String []args) 
    BinaryTree tree = new BinaryTree(); 
    tree.root = new Node(1); 
    tree.root.left = new Node(2); 
    tree.root.right = new Node(3); 
  
    Console.WriteLine("Density of given "
                      "Binary Tree is : "
                  tree.density(tree.root)); 
  
// This code is contributed 
// by Arnab Kundu

Output:

Density of given binary tree is 1.5

Reference:
http://www.eem.anadolu.edu.tr/egermen/EEM%20480/icerik/EEM%20480%20Algorithms%20and%20Complexity%20Week%208.pdf



This article is attributed to GeeksforGeeks.org

tags:

Tree Tree

leave a comment

code

0 Comments

load comments

Subscribe to Our Newsletter