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

Categories
Relative Post