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