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
leave a comment
0 Comments