Density Of Binary Tree In One Traversal

Introduction

A binary tree is a tree data structure in which each node has at most two children nodes. The children nodes are called the left node and the right node. 

Problem Statement: In this article, we will be finding the density of a given binary tree using one traversal.

The density of a binary tree can be calculated using the following formula,

Density of binary tree = Total number of nodes/height of the binary tree

Example

Input: 

9
            / \
          8   7

Output: 

Height: 1.5

Explanation:

Number of nodes in the binary tree: 3
Height of the binary tree: 2
Density: 3/2

Solution

We can easily solve this problem by first finding the height and then the size of the binary tree. We can then find the ratio of the two, which is the required output. We will use recursion to find the height and the size of the binary tree.

Algorithm

Step 1: Create a binary tree.

Step 2: Find the number of nodes in the binary tree using a recursive function.

Step 3: Find the height of the binary tree using a recursive function.

Step 4: Find the ratio of the number of nodes and the height.

Step 5: Display the ratio as the density of the binary tree. 

Code

//Class to determine the characteristics of nodes in a binary tree
class Node{
	int data;
	Node left, right;
	public Node(int data){
		this.data = data;
		left = right = null;	
	}
}

//Class to initialize size of the binary tree
class Size{
	int size = 0;
}

class Solution{
	Node root;
	//Recursive function to calculate the height and the size
	int heighAndSize(Node root, Size size){
		//Returning 0 if the binary tree is null
		if (root == null)
			return 0;
		int left = heighAndSize(root.left, size);
		int right = heighAndSize(root.right, size);
		Size.size++;
		//Comparing the height of the left and right subtree
		//and returning the greater of the two
		return (left > right) ? left + 1 : right + 1;
	}
	//Function to return the density of the binary tree
	float density(Node root){
		Size size = new Size();
		if (root == null)
		return 0;
		int height = heighAndSize(root, size);
		System.out.println("\nNumber of nodes in given Binary Tree are : " + size.size);
		System.out.println("\nHeight of given Binary Tree is : " + height);
		return (float) size.size / height;
	}
	//Driver Function
	public static void main(String[] args){
		Solution tree = new Solution();
		tree.root = new Node(9);
		tree.root.left = new Node(8);
		tree.root.right = new Node(7);
		tree.root.left.left = new Node(6);
		tree.root.left.right = new Node(5);
		System.out.println("\nDensity of given Binary Tree is : " + tree.density(tree.root));
	}
}

You can also try this code with Online Java Compiler

Run Code

Complexities

The time complexity for this algorithm is O(log n), where n is the number of nodes.

The space complexity for this algorithm is O(n), where n is the number of nodes.

Check out this problem - Mirror A Binary Tree