Skip to main content

Print all the leaf nodes of binary heap

In computer science, a binary heap is a specialized tree-based data structure that satisfies the heap property. Binary heaps are commonly used to implement priority queues and can be visualized as a complete binary tree, where each node has a value that is less than or equal to the values of its children (in a min heap). In this article, we'll explore how to print all the leaf nodes of a binary heap using a C program.

Problem Statement

The problem is to print all the leaf nodes of a given binary heap. A leaf node is a node in the binary heap that does not have any children.

Example

Build min heap using following array : [4 , 7 , 8 , 2 , 9 , 3 , 1 , 6 , 10]

Consider the following binary heap:

         1
        /   \
       /     \
      2       3
     /  \    /  \
    6    9  4    8
   / \   
  7   10

The leaf nodes of this binary heap are: 7, 10, 9, 4, and 8.

Idea to Solve the Problem

To solve this problem, we can use a recursive approach. We will traverse the binary heap starting from the root node and recursively visit its left and right children. When we encounter a node that does not have any children (i.e., a leaf node), we will print its value.

Pseudocode

function printLeafNodes(node, size, root):
    if root < size:
        if left child of root is out of bounds and right child of root is out of bounds:
            print value of node[root]
        recursively call printLeafNodes for left child of root
        recursively call printLeafNodes for right child of root

buildMinHeap(arr, size)  // Constructs the min heap
printLeafNodes(arr, size, 0)  // Prints leaf nodes

Algorithm Explanation

  1. We start by constructing the min heap using the buildMinHeap function, which rearranges the array elements to satisfy the min heap property.
  2. Next, we call the printLeafNodes function with the array arr, its size size, and the root index 0.
  3. Inside the printLeafNodes function, we check if the current root is within bounds. If it is not, we return.
  4. If the left child and right child of the current root are out of bounds (i.e., there are no children), we print the value of the current node[root].
  5. We then recursively call the printLeafNodes function for the left child and the right child of the current root.
  6. The recursive calls continue until we have visited all the nodes in the heap.

Code Solution

// C Program
// Print all the leaf nodes of binary heap
#include <stdio.h>

//Swap two element in array
void swap(int arr[], int first, int second)
{
	int auxiliary = arr[first];
	arr[first] = arr[second];
	arr[second] = auxiliary;
}
// This is converting given root and its leaf into a valid min heap form
void minHeap(int arr[], int size, int root)
{
	int left = 2 *root + 1;
	int right = 2 *root + 2;
	int task = -1;
	if (left < size && arr[left] < arr[root])
	{
		if (right < size && arr[right] < arr[left])
		{
			// When right child is less than left child
			swap(arr, right, root);
			task = right;
		}
		else
		{
			// When left child is less than root node
			swap(arr, left, root);
			task = left;
		}
	}
	else if (right < size && arr[right] < arr[root])
	{
		// When right child is less than root node
		swap(arr, right, root);
		task = right;
	}
	if (task != -1)
	{
		// Execute function until when changes are required
		minHeap(arr, size, task);
	}
}
// Show array elements
void printData(int arr[], int size)
{
	printf("\n");
	for (int i = 0; i < size; i++)
	{
		printf("%3d", arr[i]);
	}
}
// Display leaf nodes
void leafNodes(int node[], int size, int root)
{
	if (root < size)
	{
		if ((2 *root + 1) >= size && (2 *root + 2) >= size)
		{
			printf("%3d", node[root]);
		}
		// Recursive visit to child node
		leafNodes(node, size, 2 *root + 1);
		leafNodes(node, size, 2 *root + 2);
	}
}
// Handles the request of construct min heap in given array
void buildMinHeap(int arr[], int size)
{
	for (int i = (size / 2); i >= 0; i--)
	{
		minHeap(arr, size, i);
	}
}
int main()
{
	// Array elements
	int arr[] = {
		4 , 7 , 8 , 2 , 9 , 3 , 1 , 6 , 10
	};
	// Find number of element in array
	int size = sizeof(arr) / sizeof(arr[0]);
	buildMinHeap(arr, size);
	/*
	    Construct Min heap

	          1
	        /   \
	       /     \
	      2       3
	     /  \    /  \
	    6    9  4    8
	   / \   
	  7   10 
	*/
	printf("\n Construct Min Heap ");
	//Display heap elements
	printData(arr, size);
	printf("\n Leaf nodes \n");
	leafNodes(arr, size, 0);
	return 0;
}

Output

 Construct Min Heap
  1  2  3  6  9  4  8  7 10
 Leaf nodes
  7 10  9  4  8
/*
  Java program
  Print all the leaf nodes of binary heap
*/
public class MinHeap
{
	//Swap two element in array
	public void swap(int[] arr, int first, int second)
	{
		int auxiliary = arr[first];
		arr[first] = arr[second];
		arr[second] = auxiliary;
	}
	// This is converting given root and its leaf into a valid min heap form
	public void minHeap(int[] arr, int size, int root)
	{
		int left = 2 * root + 1;
		int right = 2 * root + 2;
		int task = -1;
		if (left < size && arr[left] < arr[root])
		{
			if (right < size && arr[right] < arr[left])
			{
				// When right child is less than left child
				swap(arr, right, root);
				task = right;
			}
			else
			{
				// When left child is less than root node
				swap(arr, left, root);
				task = left;
			}
		}
		else if (right < size && arr[right] < arr[root])
		{
			// When right child is less than root node
			swap(arr, right, root);
			task = right;
		}
		if (task != -1)
		{
			// Execute function until when changes are required
			minHeap(arr, size, task);
		}
	}
	// Show array elements
	public void printData(int[] arr, int size)
	{
		System.out.print("\n");
		for (int i = 0; i < size; i++)
		{
			System.out.print("  " + arr[i]);
		}
	}
	// Display leaf nodes
	public void leafNodes(int[] node, int size, int root)
	{
		if (root < size)
		{
			if ((2 * root + 1) >= size && (2 * root + 2) >= size)
			{
				System.out.print("  " + node[root]);
			}
			// Recursive visit to child node
			leafNodes(node, size, 2 * root + 1);
			leafNodes(node, size, 2 * root + 2);
		}
	}
	// Handles the request of construct min heap in given array
	public void buildMinHeap(int[] arr, int size)
	{
		for (int i = (size / 2); i >= 0; i--)
		{
			minHeap(arr, size, i);
		}
	}
	public static void main(String[] args)
	{
		MinHeap task = new MinHeap();
		// Array elements
		int[] arr = {
			4 , 7 , 8 , 2 , 9 , 3 , 1 , 6 , 10
		};
		// Find number of element in array
		int size = arr.length;
		task.buildMinHeap(arr, size);
		/*
		    Construct Min heap

		          1
		        /   \
		       /     \
		      2       3
		     /  \    /  \
		    6    9  4    8
		   / \   
		  7   10 
		*/
		System.out.print("\n Construct Min Heap ");
		//Display heap elements
		task.printData(arr, size);
		System.out.print("\n Leaf nodes \n");
		task.leafNodes(arr, size, 0);
	}
}

Output

 Construct Min Heap
  1  2  3  6  9  4  8  7  10
 Leaf nodes
  7  10  9  4  8
// Include header file
#include <iostream>

using namespace std;
/*
  C++ program
  Print all the leaf nodes of binary heap
*/
class MinHeap
{
	public:
		//Swap two element in array
		void swap(int arr[], int first, int second)
		{
			int auxiliary = arr[first];
			arr[first] = arr[second];
			arr[second] = auxiliary;
		}
	// This is converting given root and its leaf into a valid min heap form
	void minHeap(int arr[], int size, int root)
	{
		int left = 2 *root + 1;
		int right = 2 *root + 2;
		int task = -1;
		if (left < size && arr[left] < arr[root])
		{
			if (right < size && arr[right] < arr[left])
			{
				// When right child is less than left child
				this->swap(arr, right, root);
				task = right;
			}
			else
			{
				// When left child is less than root node
				this->swap(arr, left, root);
				task = left;
			}
		}
		else if (right < size && arr[right] < arr[root])
		{
			// When right child is less than root node
			this->swap(arr, right, root);
			task = right;
		}
		if (task != -1)
		{
			// Execute function until when changes are required
			this->minHeap(arr, size, task);
		}
	}
	// Show array elements
	void printData(int arr[], int size)
	{
		cout << "\n";
		for (int i = 0; i < size; i++)
		{
			cout << "  " << arr[i];
		}
	}
	// Display leaf nodes
	void leafNodes(int node[], int size, int root)
	{
		if (root < size)
		{
			if ((2 *root + 1) >= size && (2 *root + 2) >= size)
			{
				cout << "  " << node[root];
			}
			// Recursive visit to child node
			this->leafNodes(node, size, 2 *root + 1);
			this->leafNodes(node, size, 2 *root + 2);
		}
	}
	// Handles the request of construct min heap in given array
	void buildMinHeap(int arr[], int size)
	{
		for (int i = (size / 2); i >= 0; i--)
		{
			this->minHeap(arr, size, i);
		}
	}
};
int main()
{
	MinHeap task = MinHeap();
	// Array elements
	int arr[] = {
		4 , 7 , 8 , 2 , 9 , 3 , 1 , 6 , 10
	};
	// Find number of element in array
	int size = sizeof(arr) / sizeof(arr[0]);
	task.buildMinHeap(arr, size);
	/*
	    Construct Min heap
	          1
	        /   \
	       /     \
	      2       3
	     /  \    /  \
	    6    9  4    8
	   / \   
	  7   10 
	*/
	cout << "\n Construct Min Heap ";
	//Display heap elements
	task.printData(arr, size);
	cout << "\n Leaf nodes \n";
	task.leafNodes(arr, size, 0);
	return 0;
}

Output

 Construct Min Heap
  1  2  3  6  9  4  8  7  10
 Leaf nodes
  7  10  9  4  8
// Include namespace system
using System;
/*
  C# program
  Print all the leaf nodes of binary heap
*/
public class MinHeap
{
	//Swap two element in array
	public void swap(int[] arr, int first, int second)
	{
		int auxiliary = arr[first];
		arr[first] = arr[second];
		arr[second] = auxiliary;
	}
	// This is converting given root and its leaf into a valid min heap form
	public void minHeap(int[] arr, int size, int root)
	{
		int left = 2 * root + 1;
		int right = 2 * root + 2;
		int task = -1;
		if (left < size && arr[left] < arr[root])
		{
			if (right < size && arr[right] < arr[left])
			{
				// When right child is less than left child
				swap(arr, right, root);
				task = right;
			}
			else
			{
				// When left child is less than root node
				swap(arr, left, root);
				task = left;
			}
		}
		else if (right < size && arr[right] < arr[root])
		{
			// When right child is less than root node
			swap(arr, right, root);
			task = right;
		}
		if (task != -1)
		{
			// Execute function until when changes are required
			minHeap(arr, size, task);
		}
	}
	// Show array elements
	public void printData(int[] arr, int size)
	{
		Console.Write("\n");
		for (int i = 0; i < size; i++)
		{
			Console.Write("  " + arr[i]);
		}
	}
	// Display leaf nodes
	public void leafNodes(int[] node, int size, int root)
	{
		if (root < size)
		{
			if ((2 * root + 1) >= size && (2 * root + 2) >= size)
			{
				Console.Write("  " + node[root]);
			}
			// Recursive visit to child node
			leafNodes(node, size, 2 * root + 1);
			leafNodes(node, size, 2 * root + 2);
		}
	}
	// Handles the request of construct min heap in given array
	public void buildMinHeap(int[] arr, int size)
	{
		for (int i = (size / 2); i >= 0; i--)
		{
			minHeap(arr, size, i);
		}
	}
	public static void Main(String[] args)
	{
		MinHeap task = new MinHeap();
		// Array elements
		int[] arr = {
			4 , 7 , 8 , 2 , 9 , 3 , 1 , 6 , 10
		};
		// Find number of element in array
		int size = arr.Length;
		task.buildMinHeap(arr, size);
		/*
		    Construct Min heap
		          1
		        /   \
		       /     \
		      2       3
		     /  \    /  \
		    6    9  4    8
		   / \   
		  7   10 
		*/
		Console.Write("\n Construct Min Heap ");
		//Display heap elements
		task.printData(arr, size);
		Console.Write("\n Leaf nodes \n");
		task.leafNodes(arr, size, 0);
	}
}

Output

 Construct Min Heap
  1  2  3  6  9  4  8  7  10
 Leaf nodes
  7  10  9  4  8
<?php
/*
  Php program
  Print all the leaf nodes of binary heap
*/
class MinHeapTree
{
	//Swap two element in array
	public	function swap( & $arr, $first, $second)
	{
		$auxiliary = $arr[$first];
		$arr[$first] = $arr[$second];
		$arr[$second] = $auxiliary;
	}
	// This is converting given root and its leaf into a valid min heap form
	public	function minHeap( & $arr, $size, $root)
	{
		$left = 2 * $root + 1;
		$right = 2 * $root + 2;
		$task = -1;
		if ($left < $size && $arr[$left] < $arr[$root])
		{
			if ($right < $size && $arr[$right] < $arr[$left])
			{
				// When right child is less than left child
				$this->swap($arr, $right, $root);
				$task = $right;
			}
			else
			{
				// When left child is less than root node
				$this->swap($arr, $left, $root);
				$task = $left;
			}
		}
		else if ($right < $size && $arr[$right] < $arr[$root])
		{
			// When right child is less than root node
			$this->swap($arr, $right, $root);
			$task = $right;
		}
		if ($task != -1)
		{
			// Execute function until when changes are required
			$this->minHeap($arr, $size, $task);
		}
	}
	// Show array elements
	public	function printData( & $arr, $size)
	{
		echo "\n";
		for ($i = 0; $i < $size; $i++)
		{
			echo "  ". $arr[$i];
		}
	}
	// Display leaf nodes
	public	function leafNodes( & $node, $size, $root)
	{
		if ($root < $size)
		{
			if ((2 * $root + 1) >= $size && (2 * $root + 2) >= $size)
			{
				echo "  ". $node[$root];
			}
			// Recursive visit to child node
			$this->leafNodes($node, $size, 2 * $root + 1);
			$this->leafNodes($node, $size, 2 * $root + 2);
		}
	}
	// Handles the request of construct min heap in given array
	public	function buildMinHeap( & $arr, $size)
	{
		for ($i = (intval($size / 2)); $i >= 0; $i--)
		{
			$this->minHeap($arr, $size, $i);
		}
	}
}

function main()
{
	$task = new MinHeapTree();
	// Array elements
	$arr = array(4, 7, 8, 2, 9, 3, 1, 6, 10);
	// Find number of element in array
	$size = count($arr);
	$task->buildMinHeap($arr, $size);
	/*
	    Construct Min heap
	          1
	        /   \
	       /     \
	      2       3
	     /  \    /  \
	    6    9  4    8
	   / \   
	  7   10 
	*/
	echo "\n Construct Min Heap ";
	//Display heap elements
	$task->printData($arr, $size);
	echo "\n Leaf nodes \n";
	$task->leafNodes($arr, $size, 0);
}
main();

Output

 Construct Min Heap
  1  2  3  6  9  4  8  7  10
 Leaf nodes
  7  10  9  4  8
/*
  Node Js program
  Print all the leaf nodes of binary heap
*/
class MinHeapTree
{
	//Swap two element in array
	swap(arr, first, second)
	{
		var auxiliary = arr[first];
		arr[first] = arr[second];
		arr[second] = auxiliary;
	}
	// This is converting given root and its leaf into a valid min heap form
	minHeap(arr, size, root)
	{
		var left = 2 * root + 1;
		var right = 2 * root + 2;
		var task = -1;
		if (left < size && arr[left] < arr[root])
		{
			if (right < size && arr[right] < arr[left])
			{
				// When right child is less than left child
				this.swap(arr, right, root);
				task = right;
			}
			else
			{
				// When left child is less than root node
				this.swap(arr, left, root);
				task = left;
			}
		}
		else if (right < size && arr[right] < arr[root])
		{
			// When right child is less than root node
			this.swap(arr, right, root);
			task = right;
		}
		if (task != -1)
		{
			// Execute function until when changes are required
			this.minHeap(arr, size, task);
		}
	}
	// Show array elements
	printData(arr, size)
	{
		process.stdout.write("\n");
		for (var i = 0; i < size; i++)
		{
			process.stdout.write("  " + arr[i]);
		}
	}
	// Display leaf nodes
	leafNodes(node, size, root)
	{
		if (root < size)
		{
			if ((2 * root + 1) >= size && (2 * root + 2) >= size)
			{
				process.stdout.write("  " + node[root]);
			}
			// Recursive visit to child node
			this.leafNodes(node, size, 2 * root + 1);
			this.leafNodes(node, size, 2 * root + 2);
		}
	}
	// Handles the request of construct min heap in given array
	buildMinHeap(arr, size)
	{
		for (var i = (parseInt(size / 2)); i >= 0; i--)
		{
			this.minHeap(arr, size, i);
		}
	}
}

function main()
{
	var task = new MinHeapTree();
	// Array elements
	var arr = [4, 7, 8, 2, 9, 3, 1, 6, 10];
	// Find number of element in array
	var size = arr.length;
	task.buildMinHeap(arr, size);
	/*
	    Construct Min heap
	          1
	        /   \
	       /     \
	      2       3
	     /  \    /  \
	    6    9  4    8
	   / \   
	  7   10 
	*/
	process.stdout.write("\n Construct Min Heap ");
	//Display heap elements
	task.printData(arr, size);
	process.stdout.write("\n Leaf nodes \n");
	task.leafNodes(arr, size, 0);
}
main();

Output

 Construct Min Heap
  1  2  3  6  9  4  8  7  10
 Leaf nodes
  7  10  9  4  8
#   Python 3 program
#   Print all the leaf nodes of binary heap

class MinHeapTree :
	# Swap two element in array
	def swap(self, arr, first, second) :
		auxiliary = arr[first]
		arr[first] = arr[second]
		arr[second] = auxiliary
	
	#  This is converting given root and its leaf into a valid min heap form
	def minHeap(self, arr, size, root) :
		left = 2 * root + 1
		right = 2 * root + 2
		task = -1
		if (left < size and arr[left] < arr[root]) :
			if (right < size and arr[right] < arr[left]) :
				#  When right child is less than left child
				self.swap(arr, right, root)
				task = right
			else :
				#  When left child is less than root node
				self.swap(arr, left, root)
				task = left
			
		
		elif(right < size and arr[right] < arr[root]) :
			#  When right child is less than root node
			self.swap(arr, right, root)
			task = right
		
		if (task != -1) :
			#  Execute function until when changes are required
			self.minHeap(arr, size, task)
		
	
	#  Show array elements
	def printData(self, arr, size) :
		print(end = "\n")
		i = 0
		while (i < size) :
			print("  ", arr[i], end = "")
			i += 1
		
	
	#  Display leaf nodes
	def leafNodes(self, node, size, root) :
		if (root < size) :
			if ((2 * root + 1) >= size and(2 * root + 2) >= size) :
				print("  ", node[root], end = "")
			
			#  Recursive visit to child node
			self.leafNodes(node, size, 2 * root + 1)
			self.leafNodes(node, size, 2 * root + 2)
		
	
	#  Handles the request of construct min heap in given array
	def buildMinHeap(self, arr, size) :
		i = (int(size / 2))
		while (i >= 0) :
			self.minHeap(arr, size, i)
			i -= 1
		
	

def main() :
	task = MinHeapTree()
	#  Array elements
	arr = [4, 7, 8, 2, 9, 3, 1, 6, 10]
	#  Find number of element in array
	size = len(arr)
	task.buildMinHeap(arr, size)
	# 
	#     Construct Min heap
	#           1
	#         /   \
	#        /     \
	#       2       3
	#      /  \    /  \
	#     6    9  4    8
	#    / \   
	#   7   10 
	
	print("\n Construct Min Heap ", end = "")
	# Display heap elements
	task.printData(arr, size)
	print("\n Leaf nodes ")
	task.leafNodes(arr, size, 0)

if __name__ == "__main__": main()

Output

 Construct Min Heap
   1   2   3   6   9   4   8   7   10
 Leaf nodes
   7   10   9   4   8
#   Ruby program
#   Print all the leaf nodes of binary heap

class MinHeapTree 
	# Swap two element in array
	def swap(arr, first, second) 
		auxiliary = arr[first]
		arr[first] = arr[second]
		arr[second] = auxiliary
	end

	#  This is converting given root and its leaf into a valid min heap form
	def minHeap(arr, size, root) 
		left = 2 * root + 1
		right = 2 * root + 2
		task = -1
		if (left < size && arr[left] < arr[root]) 
			if (right < size && arr[right] < arr[left]) 
				#  When right child is less than left child
				self.swap(arr, right, root)
				task = right
			else 
				#  When left child is less than root node
				self.swap(arr, left, root)
				task = left
			end

		elsif(right < size && arr[right] < arr[root]) 
			#  When right child is less than root node
			self.swap(arr, right, root)
			task = right
		end

		if (task != -1) 
			#  Execute function until when changes are required
			self.minHeap(arr, size, task)
		end

	end

	#  Show array elements
	def printData(arr, size) 
		print("\n")
		i = 0
		while (i < size) 
			print("  ", arr[i])
			i += 1
		end

	end

	#  Display leaf nodes
	def leafNodes(node, size, root) 
		if (root < size) 
			if ((2 * root + 1) >= size && (2 * root + 2) >= size) 
				print("  ", node[root])
			end

			#  Recursive visit to child node
			self.leafNodes(node, size, 2 * root + 1)
			self.leafNodes(node, size, 2 * root + 2)
		end

	end

	#  Handles the request of construct min heap in given array
	def buildMinHeap(arr, size) 
		i = (size / 2)
		while (i >= 0) 
			self.minHeap(arr, size, i)
			i -= 1
		end

	end

end

def main() 
	task = MinHeapTree.new()
	#  Array elements
	arr = [4, 7, 8, 2, 9, 3, 1, 6, 10]
	#  Find number of element in array
	size = arr.length
	task.buildMinHeap(arr, size)
	# 
	#     Construct Min heap
	#           1
	#         /   \
	#        /     \
	#       2       3
	#      /  \    /  \
	#     6    9  4    8
	#    / \   
	#   7   10 
	
	print("\n Construct Min Heap ")
	# Display heap elements
	task.printData(arr, size)
	print("\n Leaf nodes \n")
	task.leafNodes(arr, size, 0)
end

main()

Output

 Construct Min Heap 
  1  2  3  6  9  4  8  7  10
 Leaf nodes 
  7  10  9  4  8
/*
  Scala program
  Print all the leaf nodes of binary heap
*/
class MinHeapTree
{
	//Swap two element in array
	def swap(arr: Array[Int], first: Int, second: Int): Unit = {
		var auxiliary: Int = arr(first);
		arr(first) = arr(second);
		arr(second) = auxiliary;
	}
	// This is converting given root and its leaf into a valid min heap form
	def minHeap(arr: Array[Int], size: Int, root: Int): Unit = {
		var left: Int = 2 * root + 1;
		var right: Int = 2 * root + 2;
		var task: Int = -1;
		if (left < size && arr(left) < arr(root))
		{
			if (right < size && arr(right) < arr(left))
			{
				// When right child is less than left child
				this.swap(arr, right, root);
				task = right;
			}
			else
			{
				// When left child is less than root node
				this.swap(arr, left, root);
				task = left;
			}
		}
		else if (right < size && arr(right) < arr(root))
		{
			// When right child is less than root node
			this.swap(arr, right, root);
			task = right;
		}
		if (task != -1)
		{
			// Execute function until when changes are required
			this.minHeap(arr, size, task);
		}
	}
	// Show array elements
	def printData(arr: Array[Int], size: Int): Unit = {
		print("\n");
		var i: Int = 0;
		while (i < size)
		{
			print("  " + arr(i));
			i += 1;
		}
	}
	// Display leaf nodes
	def leafNodes(node: Array[Int], size: Int, root: Int): Unit = {
		if (root < size)
		{
			if ((2 * root + 1) >= size && (2 * root + 2) >= size)
			{
				print("  " + node(root));
			}
			// Recursive visit to child node
			this.leafNodes(node, size, 2 * root + 1);
			this.leafNodes(node, size, 2 * root + 2);
		}
	}
	// Handles the request of construct min heap in given array
	def buildMinHeap(arr: Array[Int], size: Int): Unit = {
		var i: Int = ((size / 2).toInt);
		while (i >= 0)
		{
			this.minHeap(arr, size, i);
			i -= 1;
		}
	}
}
object Main
{
	def main(args: Array[String]): Unit = {
		var task: MinHeapTree = new MinHeapTree();
		// Array elements
		var arr: Array[Int] = Array(4, 7, 8, 2, 9, 3, 1, 6, 10);
		// Find number of element in array
		var size: Int = arr.length;
		task.buildMinHeap(arr, size);
		/*
		    Construct Min heap
		          1
		        /   \
		       /     \
		      2       3
		     /  \    /  \
		    6    9  4    8
		   / \   
		  7   10 
		*/
		print("\n Construct Min Heap ");
		//Display heap elements
		task.printData(arr, size);
		print("\n Leaf nodes \n");
		task.leafNodes(arr, size, 0);
	}
}

Output

 Construct Min Heap
  1  2  3  6  9  4  8  7  10
 Leaf nodes
  7  10  9  4  8
/*
  Swift 4 program
  Print all the leaf nodes of binary heap
*/
class MinHeapTree
{
	//Swap two element in array
	func swap(_ arr: inout[Int], _ first: Int, _ second: Int)
	{
		let auxiliary: Int = arr[first];
		arr[first] = arr[second];
		arr[second] = auxiliary;
	}
	// This is converting given root and its leaf into a valid min heap form
	func minHeap(_ arr: inout[Int], _ size: Int, _ root: Int)
	{
		let left: Int = 2 * root + 1;
		let right: Int = 2 * root + 2;
		var task: Int = -1;
		if (left < size && arr[left] < arr[root])
		{
			if (right < size && arr[right] < arr[left])
			{
				// When right child is less than left child
				self.swap(&arr, right, root);
				task = right;
			}
			else
			{
				// When left child is less than root node
				self.swap(&arr, left, root);
				task = left;
			}
		}
		else if (right < size && arr[right] < arr[root])
		{
			// When right child is less than root node
			self.swap(&arr, right, root);
			task = right;
		}
		if (task  != -1)
		{
			// Execute function until when changes are required
			self.minHeap(&arr, size, task);
		}
	}
	// Show array elements
	func printData(_ arr: [Int], _ size: Int)
	{
		print(terminator: "\n");
		var i: Int = 0;
		while (i < size)
		{
			print("  ", arr[i], terminator: "");
			i += 1;
		}
	}
	// Display leaf nodes
	func leafNodes(_ node: [Int], _ size: Int, _ root: Int)
	{
		if (root < size)
		{
			if ((2 * root + 1) >= size && (2 * root + 2) >= size)
			{
				print("  ", node[root], terminator: "");
			}
			// Recursive visit to child node
			self.leafNodes(node, size, 2 * root + 1);
			self.leafNodes(node, size, 2 * root + 2);
		}
	}
	// Handles the request of construct min heap in given array
	func buildMinHeap(_ arr: inout[Int], _ size: Int)
	{
		var i: Int = (size / 2);
		while (i >= 0)
		{
			self.minHeap(&arr, size, i);
			i -= 1;
		}
	}
}
func main()
{
	let task: MinHeapTree = MinHeapTree();
	// Array elements
	var arr: [Int] = [4, 7, 8, 2, 9, 3, 1, 6, 10];
	// Find number of element in array
	let size: Int = arr.count;
	task.buildMinHeap(&arr, size);
	/*
	    Construct Min heap
	          1
	        /   \
	       /     \
	      2       3
	     /  \    /  \
	    6    9  4    8
	   / \   
	  7   10 
	*/
	print("\n Construct Min Heap ", terminator: "");
	//Display heap elements
	task.printData(arr, size);
	print("\n Leaf nodes ");
	task.leafNodes(arr, size, 0);
}
main();

Output

 Construct Min Heap
   1   2   3   6   9   4   8   7   10
 Leaf nodes
   7   10   9   4   8
/*
  Kotlin program
  Print all the leaf nodes of binary heap
*/
class MinHeapTree
{
	//Swap two element in array
	fun swap(arr: Array <Int> , first: Int, second: Int): Unit
	{
		var auxiliary: Int = arr[first];
		arr[first] = arr[second];
		arr[second] = auxiliary;
	}
	// This is converting given root and its leaf into a valid min heap form
	fun minHeap(arr: Array <Int> , size: Int, root: Int): Unit
	{
		var left: Int = 2 * root + 1;
		var right: Int = 2 * root + 2;
		var task: Int = -1;
		if (left < size && arr[left] < arr[root])
		{
			if (right < size && arr[right] < arr[left])
			{
				// When right child is less than left child
				this.swap(arr, right, root);
				task = right;
			}
			else
			{
				// When left child is less than root node
				this.swap(arr, left, root);
				task = left;
			}
		}
		else if (right < size && arr[right] < arr[root])
		{
			// When right child is less than root node
			this.swap(arr, right, root);
			task = right;
		}
		if (task != -1)
		{
			// Execute function until when changes are required
			this.minHeap(arr, size, task);
		}
	}
	// Show array elements
	fun printData(arr: Array < Int > , size: Int): Unit
	{
		print("\n");
		var i: Int = 0;
		while (i < size)
		{
			print("  " + arr[i]);
			i += 1;
		}
	}
	// Display leaf nodes
	fun leafNodes(node: Array < Int > , size: Int, root: Int): Unit
	{
		if (root < size)
		{
			if ((2 * root + 1) >= size && (2 * root + 2) >= size)
			{
				print("  " + node[root]);
			}
			// Recursive visit to child node
			this.leafNodes(node, size, 2 * root + 1);
			this.leafNodes(node, size, 2 * root + 2);
		}
	}
	// Handles the request of construct min heap in given array
	fun buildMinHeap(arr: Array < Int > , size: Int): Unit
	{
		var i: Int = (size / 2);
		while (i >= 0)
		{
			this.minHeap(arr, size, i);
			i -= 1;
		}
	}
}
fun main(args: Array <String> ): Unit
{
	var task: MinHeapTree = MinHeapTree();
	// Array elements
	var arr: Array <Int> = arrayOf(4, 7, 8, 2, 9, 3, 1, 6, 10);
	// Find number of element in array
	var size: Int = arr.count();
	task.buildMinHeap(arr, size);
	/*
	    Construct Min heap
	          1
	        /   \
	       /     \
	      2       3
	     /  \    /  \
	    6    9  4    8
	   / \   
	  7   10 
	*/
	print("\n Construct Min Heap ");
	//Display heap elements
	task.printData(arr, size);
	print("\n Leaf nodes \n");
	task.leafNodes(arr, size, 0);
}

Output

 Construct Min Heap
  1  2  3  6  9  4  8  7  10
 Leaf nodes
  7  10  9  4  8

Time Complexity

The time complexity of constructing the min heap using buildMinHeap is O(n), where n is the number of elements in the heap. The time complexity of printing the leaf nodes using printLeafNodes is also O(n), as each node is visited exactly once. Therefore, the overall time complexity of the program is O(n).

Last updated on by Kalkicode




Comment

Please share your knowledge to improve code and content standard. Also submit your doubts, and test case. We improve by your feedback. We will try to resolve your query as soon as possible.

New Comment