Skip to main content

Level Order Tree Traversal Using Recursion

Level order tree traversal is a way of traversing or visiting all the nodes of a tree in a level-by-level order, where the nodes at each level are visited from left to right. In other words, it starts from the root node and visits all nodes at level 1, then all nodes at level 2, and so on until all nodes are visited.

Recursion is a programming technique where a function calls itself to solve a problem by breaking it down into smaller subproblems. In level order tree traversal using recursion, we use a recursive function to traverse the tree in level order.

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
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