Density of Binary Tree in One Traversal - GeeksforGeeks

Density of Binary Tree in One Traversal - GeeksforGeeks
Given a Binary Tree, find density of it by doing one traversal of it.

Density of Binary Tree = Size / Height 

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;

}

Read full article from Density of Binary Tree in One Traversal - GeeksforGeeks