Posted on by Kalkicode
Code Recursion

Level Order Tree Traversal Using Recursion

In this article, we will explore the concept of performing a level-order tree traversal using recursion. Level-order traversal is a popular method to visit all the nodes in a binary tree systematically, level by level, from left to right. We will start with an introduction to binary trees and the level-order traversal process. Then, we'll provide a step-by-step explanation of the recursive algorithm and its implementation using a standard pseudocode representation. Finally, we'll analyze the time complexity of the code and provide an example to illustrate the traversal process.

Introduction to Binary Trees

A binary tree is a data structure composed of nodes where each node has at most two children, commonly referred to as the left child and the right child. The topmost node in the tree is called the root. The binary tree has a hierarchical structure, and the nodes can be represented using a struct in programming languages. Each node contains a data element and pointers to its left and right children.

Level-Order Tree Traversal

Level-order tree traversal, also known as breadth-first search (BFS), involves visiting all nodes of a binary tree level by level, starting from the root and moving down the tree in a left-to-right fashion. This traversal can be accomplished using various methods, such as using a queue data structure. However, in this article, we will focus on a recursive approach to achieve the level-order traversal.

Recursive Algorithm (Pseudocode)

level_order(root):
	height = tree_height(root)
	counter = 1
	while counter <= height:
		display_level(root, counter, 1)
		counter++

display_level(root, level, counter):
	if root is NULL:
		return
	if counter equals level:
		print root.data
		return
	display_level(root.left, level, counter + 1)
	display_level(root.right, level, counter + 1)

Recursive Algorithm for Level-Order Tree Traversal

  1. Begin with a function level_order that takes the root of the binary tree as input.
  2. Inside the level_order function, find the height of the binary tree using the tree_height function.
  3. For each level, from 1 to the tree's height, call the display_level function to print the nodes at that level from left to right.
  4. The display_level function takes the root of the binary tree, the current level to display, and a counter as input.
  5. In the display_level function, check if the root is NULL; if so, return.
  6. If the counter is equal to the current level, print the data of the current node and return.
  7. If the counter is not equal to the current level, recursively call display_level on the left and right children of the current node with an incremented counter.
  8. Return to the level_order function and increment the level counter for the next iteration.
  9. Repeat steps 3 to 8 until all levels are displayed.

Program Solution

/*
  C Program 
+ Level Order Tree Traversal Using Recursion

*/
#include<stdio.h>

#include<stdlib.h>
 //structure of Binary Tree node
struct Node
{
	int data;
	struct Node *left, *right;
};
//Create a binary tree nodes
struct Node *insert(int data)
{
	//create dynamic memory to new binary tree node
	struct Node *new_node = (struct Node *) malloc(sizeof(struct Node));
	if (new_node != NULL)
	{
		//set data and pointer values
		new_node->data = data;
		new_node->left = NULL; //Initially node left-pointer is NULL
		new_node->right = NULL; //Initially node right-pointer is NULL
	}
	else
	{
		printf("Memory Overflow\n");
		exit(0); //Terminate program execution
	}
	//return reference
	return new_node;
}
//Find height of given binary tree
int tree_height(struct Node *root)
{
	if (root != NULL)
	{
		//Recursively calculating  height of tree
		int a = tree_height(root->left);
		int b = tree_height(root->right);
		//returning a height of largest subtree
		if (a > b)
		{
			return a + 1;
		}
		else
		{
			return b + 1;
		}
	}
	else
	{
		return 0;
	}
}
//Display particular level from left to right
void display_level(struct Node *root, int level, int counter)
{
	if (root == NULL)
	{
		return;
	}
	if (counter == level)
	{
		printf("%d ", root->data);
		return;
	}
	//Recursively display given level of  binary tree
	display_level(root->left, level, counter + 1);
	display_level(root->right, level, counter + 1);
}
void level_order(struct Node *root)
{
	//Find find the height of tree
	int height = tree_height(root);
	int counter = 1;
	//Display tree level from top to bottom left to right
	while (counter <= height)
	{
		display_level(root, counter, 1);
		counter++;
	}
}
int main()
{
	struct Node *root = NULL;
	/*Make A Binary Tree
	-----------------------
	           9
	         /   \
	        12    3
	       /     / \
	      4    15   6
	     /     / \
	    7     8   19
	*/
	//Insertion of binary tree nodes
	root = insert(9);
	root->left = insert(12);
	root->right = insert(3);
	root->right->right = insert(6);
	root->right->left = insert(15);
	root->left->left = insert(4);
	root->left->left->left = insert(7);
	root->right->left->left = insert(8);
	root->right->left->right = insert(19);
	//Display Tree elements
	level_order(root);
	return 0;
}

Output

9 12 3 4 15 6 7 8 19
/*
  Java Program 
  Level Order Tree Traversal Using Recursion
*/
//Binary Tree Node
class Node
{
	public int data;
	public Node left;
	public Node right;
	public Node(int value)
	{
		this.data = value;
		this.right = null;
		this.left = null;
	}
}
class BinaryTree
{
	public Node root;
	public BinaryTree()
	{
		this.root = null;
	}
	//Find height of given binary tree
	public int tree_height(Node root)
	{
		if (root != null)
		{
			//Recursively calculating  height of tree
			int a = tree_height(root.left);
			int b = tree_height(root.right);
			//returning a height of largest subtree
			if (a > b)
			{
				return a + 1;
			}
			else
			{
				return b + 1;
			}
		}
		else
		{
			return 0;
		}
	}
	//Display particular level from left to right
	public void display_level(Node root, int level, int counter)
	{
		if (root == null)
		{
			return;
		}
		if (counter == level)
		{
			System.out.print(" " + root.data);
			return;
		}
		//Recursively display given level of  binary tree
		display_level(root.left, level, counter + 1);
		display_level(root.right, level, counter + 1);
	}
	public void level_order()
	{
		//Find find the height of tree
		int height = tree_height(this.root);
		int counter = 1;
		//Display tree level from top to bottom left to right
		while (counter <= height)
		{
			display_level(this.root, counter, 1);
			counter++;
		}
	}
	public static void main(String[] args)
	{
		BinaryTree obj = new BinaryTree();
		/* Make A Binary Tree
    -------------------
               9
             /   \
            12    3
           /     / \
          4    15   6
         /     / \
        7     8   19
    */
		//Insert binary tree nodes
		obj.root = new Node(9);
		obj.root.left = new Node(12);
		obj.root.right = new Node(3);
		obj.root.right.right = new Node(6);
		obj.root.right.left = new Node(15);
		obj.root.left.left = new Node(4);
		obj.root.left.left.left = new Node(7);
		obj.root.right.left.left = new Node(8);
		obj.root.right.left.right = new Node(19);
		//Display Tree elements
		obj.level_order();
	}
}

Output

 9 12 3 4 15 6 7 8 19
//Include header file
#include <iostream>

using namespace std;
/*
  C++ Program 
  Level Order Tree Traversal Using Recursion
*/
//Binary Tree Node
class Node
{
	public: int data;
	Node * left;
	Node * right;
	Node(int value)
	{
		this->data = value;
		this->right = NULL;
		this->left = NULL;
	}
};
class BinaryTree
{
	public: Node * root;
	BinaryTree()
	{
		this->root = NULL;
	}
	//Find height of given binary tree
	int tree_height(Node * root)
	{
		if (root != NULL)
		{
			//Recursively calculating  height of tree
			int a = this->tree_height(root->left);
			int b = this->tree_height(root->right);
			//returning a height of largest subtree
			if (a > b)
			{
				return a + 1;
			}
			else
			{
				return b + 1;
			}
		}
		else
		{
			return 0;
		}
	}
	//Display particular level from left to right
	void display_level(Node * root, int level, int counter)
	{
		if (root == NULL)
		{
			return;
		}
		if (counter == level)
		{
			cout << " " << root->data;
			return;
		}
		//Recursively display given level of  binary tree
		this->display_level(root->left, level, counter + 1);
		this->display_level(root->right, level, counter + 1);
	}
	void level_order()
	{
		//Find find the height of tree
		int height = this->tree_height(this->root);
		int counter = 1;
		//Display tree level from top to bottom left to right
		while (counter <= height)
		{
			this->display_level(this->root, counter, 1);
			counter++;
		}
	}
};
int main()
{
	BinaryTree obj = BinaryTree();
	/* Make A Binary Tree
	    -------------------
	               9
	             /   \
	            12    3
	           /     / \
	          4    15   6
	         /     / \
	        7     8   19
	    */
	//Insert binary tree nodes
	obj.root = new Node(9);
	obj.root->left = new Node(12);
	obj.root->right = new Node(3);
	obj.root->right->right = new Node(6);
	obj.root->right->left = new Node(15);
	obj.root->left->left = new Node(4);
	obj.root->left->left->left = new Node(7);
	obj.root->right->left->left = new Node(8);
	obj.root->right->left->right = new Node(19);
	//Display Tree elements
	obj.level_order();
	return 0;
}

Output

 9 12 3 4 15 6 7 8 19
//Include namespace system
using System;
/*
  C# Program 
  Level Order Tree Traversal Using Recursion
*/
//Binary Tree Node
class Node
{
	public int data;
	public Node left;
	public Node right;
	public Node(int value)
	{
		this.data = value;
		this.right = null;
		this.left = null;
	}
}
class BinaryTree
{
	public Node root;
	public BinaryTree()
	{
		this.root = null;
	}
	//Find height of given binary tree
	public int tree_height(Node root)
	{
		if (root != null)
		{
			//Recursively calculating  height of tree
			int a = tree_height(root.left);
			int b = tree_height(root.right);
			//returning a height of largest subtree
			if (a > b)
			{
				return a + 1;
			}
			else
			{
				return b + 1;
			}
		}
		else
		{
			return 0;
		}
	}
	//Display particular level from left to right
	public void display_level(Node root, int level, int counter)
	{
		if (root == null)
		{
			return;
		}
		if (counter == level)
		{
			Console.Write(" " + root.data);
			return;
		}
		//Recursively display given level of  binary tree
		display_level(root.left, level, counter + 1);
		display_level(root.right, level, counter + 1);
	}
	public void level_order()
	{
		//Find find the height of tree
		int height = tree_height(this.root);
		int counter = 1;
		//Display tree level from top to bottom left to right
		while (counter <= height)
		{
			display_level(this.root, counter, 1);
			counter++;
		}
	}
	public static void Main(String[] args)
	{
		BinaryTree obj = new BinaryTree();
		/* Make A Binary Tree
		    -------------------
		               9
		             /   \
		            12    3
		           /     / \
		          4    15   6
		         /     / \
		        7     8   19
		    */
		//Insert binary tree nodes
		obj.root = new Node(9);
		obj.root.left = new Node(12);
		obj.root.right = new Node(3);
		obj.root.right.right = new Node(6);
		obj.root.right.left = new Node(15);
		obj.root.left.left = new Node(4);
		obj.root.left.left.left = new Node(7);
		obj.root.right.left.left = new Node(8);
		obj.root.right.left.right = new Node(19);
		//Display Tree elements
		obj.level_order();
	}
}

Output

 9 12 3 4 15 6 7 8 19
<?php
/*
  Php Program 
  Level Order Tree Traversal Using Recursion
*/
//Binary Tree Node
class Node
{
	public $data;
	public $left;
	public $right;

	function __construct($value)
	{
		$this->data = $value;
		$this->right = null;
		$this->left = null;
	}
}
class BinaryTree
{
	public $root;

	function __construct()
	{
		$this->root = null;
	}
	//Find height of given binary tree
	public	function tree_height($root)
	{
		if ($root != null)
		{
			//Recursively calculating  height of tree
			$a = $this->tree_height($root->left);
			$b = $this->tree_height($root->right);
			//returning a height of largest subtree
			if ($a > $b)
			{
				return $a + 1;
			}
			else
			{
				return $b + 1;
			}
		}
		else
		{
			return 0;
		}
	}
	//Display particular level from left to right
	public	function display_level($root, $level, $counter)
	{
		if ($root == null)
		{
			return;
		}
		if ($counter == $level)
		{
			echo " ". $root->data;
			return;
		}
		//Recursively display given level of  binary tree
		$this->display_level($root->left, $level, $counter + 1);
		$this->display_level($root->right, $level, $counter + 1);
	}
	public	function level_order()
	{
		//Find find the height of tree
		$height = $this->tree_height($this->root);
		$counter = 1;
		//Display tree level from top to bottom left to right
		while ($counter <= $height)
		{
			$this->display_level($this->root, $counter, 1);
			$counter++;
		}
	}
}

function main()
{
	$obj = new BinaryTree();
	/* Make A Binary Tree
	    -------------------
	               9
	             /   \
	            12    3
	           /     / \
	          4    15   6
	         /     / \
	        7     8   19
	    */
	//Insert binary tree nodes
	$obj->root = new Node(9);
	$obj->root->left = new Node(12);
	$obj->root->right = new Node(3);
	$obj->root->right->right = new Node(6);
	$obj->root->right->left = new Node(15);
	$obj->root->left->left = new Node(4);
	$obj->root->left->left->left = new Node(7);
	$obj->root->right->left->left = new Node(8);
	$obj->root->right->left->right = new Node(19);
	//Display Tree elements
	$obj->level_order();
}
main();

Output

 9 12 3 4 15 6 7 8 19
/*
  Node Js Program 
  Level Order Tree Traversal Using Recursion
*/
//Binary Tree Node
class Node
{
	constructor(value)
	{
		this.data = value;
		this.right = null;
		this.left = null;
	}
}
class BinaryTree
{
	constructor()
	{
		this.root = null;
	}
	//Find height of given binary tree
	tree_height(root)
	{
		if (root != null)
		{
			//Recursively calculating  height of tree
			var a = this.tree_height(root.left);
			var b = this.tree_height(root.right);
			//returning a height of largest subtree
			if (a > b)
			{
				return a + 1;
			}
			else
			{
				return b + 1;
			}
		}
		else
		{
			return 0;
		}
	}
	//Display particular level from left to right
	display_level(root, level, counter)
	{
		if (root == null)
		{
			return;
		}
		if (counter == level)
		{
			process.stdout.write(" " + root.data);
			return;
		}
		//Recursively display given level of  binary tree
		this.display_level(root.left, level, counter + 1);
		this.display_level(root.right, level, counter + 1);
	}
	level_order()
	{
		//Find find the height of tree
		var height = this.tree_height(this.root);
		var counter = 1;
		//Display tree level from top to bottom left to right
		while (counter <= height)
		{
			this.display_level(this.root, counter, 1);
			counter++;
		}
	}
}

function main()
{
	var obj = new BinaryTree();
	/* Make A Binary Tree
	    -------------------
	               9
	             /   \
	            12    3
	           /     / \
	          4    15   6
	         /     / \
	        7     8   19
	    */
	//Insert binary tree nodes
	obj.root = new Node(9);
	obj.root.left = new Node(12);
	obj.root.right = new Node(3);
	obj.root.right.right = new Node(6);
	obj.root.right.left = new Node(15);
	obj.root.left.left = new Node(4);
	obj.root.left.left.left = new Node(7);
	obj.root.right.left.left = new Node(8);
	obj.root.right.left.right = new Node(19);
	//Display Tree elements
	obj.level_order();
}
main();

Output

 9 12 3 4 15 6 7 8 19
#   Python Program 
#   Level Order Tree Traversal Using Recursion

# Binary Tree Node
class Node :
	
	def __init__(self, value) :
		self.data = value
		self.right = None
		self.left = None
	

class BinaryTree :
	
	def __init__(self) :
		self.root = None
	
	# Find height of given binary tree
	def tree_height(self, root) :
		if (root != None) :
			# Recursively calculating  height of tree
			a = self.tree_height(root.left)
			b = self.tree_height(root.right)
			# returning a height of largest subtree
			if (a > b) :
				return a + 1
			else :
				return b + 1
			
		else :
			return 0
		
	
	# Display particular level from left to right
	def display_level(self, root, level, counter) :
		if (root == None) :
			return
		
		if (counter == level) :
			print(" ", root.data, end = "")
			return
		
		# Recursively display given level of  binary tree
		self.display_level(root.left, level, counter + 1)
		self.display_level(root.right, level, counter + 1)
	
	def level_order(self) :
		# Find find the height of tree
		height = self.tree_height(self.root)
		counter = 1
		# Display tree level from top to bottom left to right
		while (counter <= height) :
			self.display_level(self.root, counter, 1)
			counter += 1
		
	

def main() :
	obj = BinaryTree()
	#  Make A Binary Tree
	#     -------------------
	#                9
	#              /   \
	#             12    3
	#            /     / \
	#           4    15   6
	#          /     / \
	#         7     8   19
	#     
	
	# Insert binary tree nodes
	obj.root = Node(9)
	obj.root.left = Node(12)
	obj.root.right = Node(3)
	obj.root.right.right = Node(6)
	obj.root.right.left = Node(15)
	obj.root.left.left = Node(4)
	obj.root.left.left.left = Node(7)
	obj.root.right.left.left = Node(8)
	obj.root.right.left.right = Node(19)
	# Display Tree elements
	obj.level_order()

if __name__ == "__main__": main()

Output

  9  12  3  4  15  6  7  8  19
#   Ruby Program 
#   Level Order Tree Traversal Using Recursion

# Binary Tree Node
class Node 

	# Define the accessor and reader of class Node  
	attr_reader :data, :left, :right
	attr_accessor :data, :left, :right

	def initialize(value)
	
		self.data = value
		self.right = nil
		self.left = nil
	end
end
class BinaryTree 

	# Define the accessor and reader of class BinaryTree  
	attr_reader :root
	attr_accessor :root

	def initialize()
	
		self.root = nil
	end
	# Find height of given binary tree
	def tree_height(root)
	
		if (root != nil)
		
			# Recursively calculating  height of tree
			a = self.tree_height(root.left)
			b = self.tree_height(root.right)
			# returning a height of largest subtree
			if (a > b)
			
				return a + 1
			else
			
				return b + 1
			end
		else
		
			return 0
		end
	end
	# Display particular level from left to right
	def display_level(root, level, counter)
	
		if (root == nil)
		
			return
		end
		if (counter == level)
		
			print(" ", root.data)
			return
		end
		# Recursively display given level of  binary tree
		self.display_level(root.left, level, counter + 1)
		self.display_level(root.right, level, counter + 1)
	end
	def level_order()
	
		# Find find the height of tree
		height = self.tree_height(self.root)
		counter = 1
		# Display tree level from top to bottom left to right
		while (counter <= height)
		
			self.display_level(self.root, counter, 1)
			counter += 1
		end
	end
end
def main()

	obj = BinaryTree.new()
	#  Make A Binary Tree
	#     -------------------
	#                9
	#              /   \
	#             12    3
	#            /     / \
	#           4    15   6
	#          /     / \
	#         7     8   19
	#     
	
	# Insert binary tree nodes
	obj.root = Node.new(9)
	obj.root.left = Node.new(12)
	obj.root.right = Node.new(3)
	obj.root.right.right = Node.new(6)
	obj.root.right.left = Node.new(15)
	obj.root.left.left = Node.new(4)
	obj.root.left.left.left = Node.new(7)
	obj.root.right.left.left = Node.new(8)
	obj.root.right.left.right = Node.new(19)
	# Display Tree elements
	obj.level_order()
end
main()

Output

 9 12 3 4 15 6 7 8 19
/*
  Scala Program 
  Level Order Tree Traversal Using Recursion
*/
//Binary Tree Node
class Node(var data: Int,
	var left: Node,
		var right: Node)
{
	def this(value: Int)
	{
		this(value, null, null);
	}
}
class BinaryTree(var root: Node)
{
	def this()
	{
		this(null);
	}
	//Find height of given binary tree
	def tree_height(root: Node): Int = {
		if (root != null)
		{
			//Recursively calculating  height of tree
			var a: Int = tree_height(root.left);
			var b: Int = tree_height(root.right);
			//returning a height of largest subtree
			if (a > b)
			{
				return a + 1;
			}
			else
			{
				return b + 1;
			}
		}
		else
		{
			return 0;
		}
	}
	//Display particular level from left to right
	def display_level(root: Node, level: Int, counter: Int): Unit = {
		if (root == null)
		{
			return;
		}
		if (counter == level)
		{
			print(" " + root.data);
			return;
		}
		//Recursively display given level of  binary tree
		display_level(root.left, level, counter + 1);
		display_level(root.right, level, counter + 1);
	}
	def level_order(): Unit = {
		//Find find the height of tree
		var height: Int = tree_height(this.root);
		var counter: Int = 1;
		//Display tree level from top to bottom left to right
		while (counter <= height)
		{
			display_level(this.root, counter, 1);
			counter += 1;
		}
	}
}
object Main
{
	def main(args: Array[String]): Unit = {
		var obj: BinaryTree = new BinaryTree();
		/* Make A Binary Tree
		    -------------------
		               9
		             /   \
		            12    3
		           /     / \
		          4    15   6
		         /     / \
		        7     8   19
		    */
		//Insert binary tree nodes
		obj.root = new Node(9);
		obj.root.left = new Node(12);
		obj.root.right = new Node(3);
		obj.root.right.right = new Node(6);
		obj.root.right.left = new Node(15);
		obj.root.left.left = new Node(4);
		obj.root.left.left.left = new Node(7);
		obj.root.right.left.left = new Node(8);
		obj.root.right.left.right = new Node(19);
		//Display Tree elements
		obj.level_order();
	}
}

Output

 9 12 3 4 15 6 7 8 19
/*
  Swift 4 Program 
  Level Order Tree Traversal Using Recursion
*/
//Binary Tree Node
class Node
{
	var data: Int;
	var left: Node? ;
	var right: Node? ;
	init(_ value: Int)
	{
		self.data = value;
		self.right = nil;
		self.left = nil;
	}
}
class BinaryTree
{
	var root: Node? ;
	init()
	{
		self.root = nil;
	}
	//Find height of given binary tree
	func tree_height(_ root: Node? ) -> Int
	{
		if (root != nil)
		{
			//Recursively calculating  height of tree
			let a: Int = self.tree_height(root!.left);
			let b: Int = self.tree_height(root!.right);
			//returning a height of largest subtree
			if (a > b)
			{
				return a + 1;
			}
			else
			{
				return b + 1;
			}
		}
		else
		{
			return 0;
		}
	}
	//Display particular level from left to right
	func display_level(_ root: Node? , _ level : Int, _ counter: Int)
	{
		if (root == nil)
		{
			return;
		}
		if (counter == level)
		{
			print(" ", root!.data, terminator: "");
			return;
		}
		//Recursively display given level of  binary tree
		self.display_level(root!.left, level, counter + 1);
		self.display_level(root!.right, level, counter + 1);
	}
	func level_order()
	{
		//Find find the height of tree
		let height: Int = self.tree_height(self.root);
		var counter: Int = 1;
		//Display tree level from top to bottom left to right
		while (counter <= height)
		{
			self.display_level(self.root, counter, 1);
			counter += 1;
		}
	}
}
func main()
{
	let obj: BinaryTree = BinaryTree();
	/* Make A Binary Tree
	    -------------------
	               9
	             /   \
	            12    3
	           /     / \
	          4    15   6
	         /     / \
	        7     8   19
	    */
	//Insert binary tree nodes
	obj.root = Node(9);
	obj.root!.left = Node(12);
	obj.root!.right = Node(3);
	obj.root!.right!.right = Node(6);
	obj.root!.right!.left = Node(15);
	obj.root!.left!.left = Node(4);
	obj.root!.left!.left!.left = Node(7);
	obj.root!.right!.left!.left = Node(8);
	obj.root!.right!.left!.right = Node(19);
	//Display Tree elements
	obj.level_order();
}
main();

Output

  9  12  3  4  15  6  7  8  19

Time Complexity Analysis

The time complexity of the level-order tree traversal using recursion depends on the height of the binary tree. At each level, the display_level function is called twice (for the left and right subtrees). Hence, the time complexity is proportional to the number of nodes in the binary tree, which is O(n), where n is the number of nodes in the tree.

Example

Let's consider the following binary tree as an example:


       9
     /   \
    12    3
   /     / \
  4    15   6
 /     / \
7     8   19

Using the provided code, the level-order traversal would produce the output: 9 12 3 4 15 6 7 8 19

Finally

In this article, we discussed the concept of level-order tree traversal using recursion. We explained the recursive algorithm step-by-step, along with a pseudocode representation. The level-order traversal is an essential technique to systematically explore the nodes of a binary tree, and the recursive approach provides an elegant solution to achieve it. Moreover, we analyzed the time complexity of the code and provided a real-world example to illustrate the traversal process. By understanding and implementing this algorithm, developers can efficiently traverse binary trees and perform various operations on the tree nodes.

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





Categories
Relative Post