Boundary Level order traversal of a Binary Tree
Given a Binary Tree, the task is to print all levels of this tree in Boundary Level order traversal.
Boundary Level order traversal: In this traversal, the first element of the level (starting boundary) is printed first, followed by last element (ending boundary). Then the process is repeated for the second and last-second element, till the complete level has been printed.
Examples:
Input:
1
/ \
12 13
/ \ / \
11 6 4 11
/ / \ / \
23 7 9 2 4
Output:
1
12 13
11 11 6 4
23 4 7 2 9
Input:
7
/ \
22 19
/ \ \
3 6 13
/ \ \ / \
1 5 8 1 4
/
23
Output:
7
22 19
3 13 6
1 4 5 1 8
23
Approach:
- In order to print level in Boundary Level order traversal, we need to first do the Level Order Traversal of the Binary tree to get the values at each level.
- Here a Queue data structure is used to store the levels of the Tree while doing the Level Order Traversal.
- Then for each level, the first element of the level (starting boundary) is printed first, followed by the last element (ending boundary). Then the process is repeated for the second and last-second element, till the complete level has been printed.
Below is the implementation of the above approach:
C++
// C++ program for printing a// Levels of Binary Tree in a// start end fashion#include <bits/stdc++.h>using namespace std;// A Tree nodestruct Node { int key; struct Node *left, *right;};// Utility function to create a new nodeNode* newNode(int key){ Node* temp = new Node; temp->key = key; temp->left = temp->right = NULL; return (temp);}// Utility function to print level in// start end fashionvoid printLevelUtil(struct Node* queue[], int index, int size){ while (index < size) { cout << queue[index++]->key << " " << queue[size--]->key << " "; } if (index == size) { cout << queue[index]->key << " "; } cout << endl;}// Utility function to print level in start// end fashion in a given Binary treevoid printLevel(struct Node* node, struct Node* queue[], int index, int size){ // Print root node value // as a single value in a // binary tree cout << queue[index]->key << endl; // Level order traversal of Tree while (index < size) { int curr_size = size; while (index < curr_size) { struct Node* temp = queue[index]; if (temp->left != NULL) { queue[size++] = temp->left; } if (temp->right != NULL) { queue[size++] = temp->right; } index++; } // Print level in a desire fashion printLevelUtil(queue, index, size - 1); }}// Function to find total no of nodesint findSize(struct Node* node){ if (node == NULL) return 0; return 1 + findSize(node->left) + findSize(node->right);}// Function to print level in start end// fashion in a given binary treevoid printLevelInStartEndFashion( struct Node* node){ int t_size = findSize(node); struct Node* queue[t_size]; queue[0] = node; printLevel(node, queue, 0, 1);}// Driver Codeint main(){ /* 10 / \ 13 13 / \ 14 15 / \ / \ 21 22 22 21 / 8 */ // Create Binary Tree as shown Node* root = newNode(10); root->left = newNode(13); root->right = newNode(13); root->right->left = newNode(14); root->right->right = newNode(15); root->right->left->left = newNode(21); root->right->left->right = newNode(22); root->right->right->left = newNode(22); root->right->right->right = newNode(21); root->right->right->right->left = newNode(8); // Print Levels In Start End Fashion printLevelInStartEndFashion(root); return 0;} |
Java
// Java program for printing a// Levels of Binary Tree in a// start end fashionclass GFG{ // A Tree nodestatic class Node { int key; Node left, right;}; // Utility function to create a new nodestatic Node newNode(int key){ Node temp = new Node(); temp.key = key; temp.left = temp.right = null; return (temp);} // Utility function to print level in// start end fashionstatic void printLevelUtil(Node queue[], int index, int size){ while (index < size) { System.out.print(queue[index++].key+ " " + queue[size--].key+ " "); } if (index == size) { System.out.print(queue[index].key+ " "); } System.out.println();} // Utility function to print level in start// end fashion in a given Binary treestatic void printLevel(Node node, Node queue[], int index, int size){ // Print root node value // as a single value in a // binary tree System.out.print(queue[index].key +"\n"); // Level order traversal of Tree while (index < size) { int curr_size = size; while (index < curr_size) { Node temp = queue[index]; if (temp.left != null) { queue[size++] = temp.left; } if (temp.right != null) { queue[size++] = temp.right; } index++; } // Print level in a desire fashion printLevelUtil(queue, index, size - 1); }} // Function to find total no of nodesstatic int findSize(Node node){ if (node == null) return 0; return 1 + findSize(node.left) + findSize(node.right);} // Function to print level in start end// fashion in a given binary treestatic void printLevelInStartEndFashion( Node node){ int t_size = findSize(node); Node []queue = new Node[t_size]; queue[0] = node; printLevel(node, queue, 0, 1);} // Driver Codepublic static void main(String[] args){ /* 10 / \ 13 13 / \ 14 15 / \ / \ 21 22 22 21 / 8 */ // Create Binary Tree as shown Node root = newNode(10); root.left = newNode(13); root.right = newNode(13); root.right.left = newNode(14); root.right.right = newNode(15); root.right.left.left = newNode(21); root.right.left.right = newNode(22); root.right.right.left = newNode(22); root.right.right.right = newNode(21); root.right.right.right.left = newNode(8); // Print Levels In Start End Fashion printLevelInStartEndFashion(root); }}// This code is contributed by Princi Singh |
Python3
# Python3 program for printing a# Levels of Binary Tree in a# start end fashion # A Tree nodeclass Node: def __init__(self, key): self.key = key self.left = None self.right = None # function to create a # new nodedef newNode(key): temp = Node(key); return temp; # Utility function to print # level in start end fashiondef printLevelUtil(queue, index, size): while (index < size): print(str(queue[index].key) + ' ' + str(queue[size].key), end = ' ') size -= 1 index += 1 if (index == size): print(queue[index].key, end = ' ') print() # Utility function to print # level in start end fashion # in a given Binary treedef printLevel(node, queue, index, size): # Print root node value # as a single value in a # binary tree print(queue[index].key) # Level order traversal # of Tree while (index < size): curr_size = size; while (index < curr_size): temp = queue[index]; if (temp.left != None): queue[size] = temp.left; size += 1 if (temp.right != None): queue[size] = temp.right; size += 1 index += 1 # Print level in a desire # fashion printLevelUtil(queue, index, size - 1); # Function to find total # no of nodesdef findSize(node): if (node == None): return 0; return (1 + findSize(node.left) + findSize(node.right));# Function to print level in start # end fashion in a given binary treedef printLevelInStartEndFashion(node): t_size = findSize(node); queue=[0 for i in range(t_size)]; queue[0] = node; printLevel(node, queue, 0, 1);# Driver code if __name__=="__main__": ''' 10 / \ 13 13 / \ 14 15 / \ / \ 21 22 22 21 / 8 ''' # Create Binary Tree as shown root = newNode(10); root.left = newNode(13); root.right = newNode(13); root.right.left = newNode(14); root.right.right = newNode(15); root.right.left.left = newNode(21); root.right.left.right = newNode(22); root.right.right.left = newNode(22); root.right.right.right = newNode(21); root.right.right.right.left = newNode(8); # Print Levels In Start End Fashion printLevelInStartEndFashion(root);# This code is contributed by Rutvik_56 |
C#
// C# program for printing a// Levels of Binary Tree in a// start end fashionusing System;class GFG{ // A Tree nodeclass Node { public int key; public Node left, right;}; // Utility function to create a new nodestatic Node newNode(int key){ Node temp = new Node(); temp.key = key; temp.left = temp.right = null; return (temp);} // Utility function to print level in// start end fashionstatic void printLevelUtil(Node []queue, int index, int size){ while (index < size) { Console.Write(queue[index++].key+ " " + queue[size--].key+ " "); } if (index == size) { Console.Write(queue[index].key+ " "); } Console.WriteLine();} // Utility function to print level in start// end fashion in a given Binary treestatic void printLevel(Node node, Node []queue, int index, int size){ // Print root node value // as a single value in a // binary tree Console.Write(queue[index].key +"\n"); // Level order traversal of Tree while (index < size) { int curr_size = size; while (index < curr_size) { Node temp = queue[index]; if (temp.left != null) { queue[size++] = temp.left; } if (temp.right != null) { queue[size++] = temp.right; } index++; } // Print level in a desire fashion printLevelUtil(queue, index, size - 1); }} // Function to find total no of nodesstatic int findSize(Node node){ if (node == null) return 0; return 1 + findSize(node.left) + findSize(node.right);} // Function to print level in start end// fashion in a given binary treestatic void printLevelInStartEndFashion( Node node){ int t_size = findSize(node); Node []queue = new Node[t_size]; queue[0] = node; printLevel(node, queue, 0, 1);} // Driver Codepublic static void Main(String[] args){ /* 10 / \ 13 13 / \ 14 15 / \ / \ 21 22 22 21 / 8 */ // Create Binary Tree as shown Node root = newNode(10); root.left = newNode(13); root.right = newNode(13); root.right.left = newNode(14); root.right.right = newNode(15); root.right.left.left = newNode(21); root.right.left.right = newNode(22); root.right.right.left = newNode(22); root.right.right.right = newNode(21); root.right.right.right.left = newNode(8); // Print Levels In Start End Fashion printLevelInStartEndFashion(root);}}// This code is contributed by PrinciRaj1992 |
Javascript
<script>// JavaScript program for printing a// Levels of Binary Tree in a// start end fashion// A Tree nodeclass Node { constructor() { this.key = 0; this.left = null; this.right = null; }}; // Utility function to create a new nodefunction newNode(key){ var temp = new Node(); temp.key = key; temp.left = temp.right = null; return (temp);} // Utility function to print level in// start end fashionfunction printLevelUtil(queue, index, size){ while (index < size) { document.write(queue[index++].key+ " " + queue[size--].key+ " "); } if (index == size) { document.write(queue[index].key+ " "); } document.write("<br>");} // Utility function to print level in start// end fashion in a given Binary treefunction printLevel(node, queue, index, size){ // Print root node value // as a single value in a // binary tree document.write(queue[index].key +"<br>"); // Level order traversal of Tree while (index < size) { var curr_size = size; while (index < curr_size) { var temp = queue[index]; if (temp.left != null) { queue[size++] = temp.left; } if (temp.right != null) { queue[size++] = temp.right; } index++; } // Print level in a desire fashion printLevelUtil(queue, index, size - 1); }} // Function to find total no of nodesfunction findSize(node){ if (node == null) return 0; return 1 + findSize(node.left) + findSize(node.right);} // Function to print level in start end// fashion in a given binary treefunction printLevelInStartEndFashion( node){ var t_size = findSize(node); var queue = Array(t_size); queue[0] = node; printLevel(node, queue, 0, 1);} // Driver Code/* 10 / \ 13 13 / \ 14 15 / \ / \ 21 22 22 21 / 8 */// Create Binary Tree as shownvar root = newNode(10);root.left = newNode(13);root.right = newNode(13);root.right.left = newNode(14);root.right.right = newNode(15);root.right.left.left = newNode(21);root.right.left.right = newNode(22);root.right.right.left = newNode(22);root.right.right.right = newNode(21);root.right.right.right.left = newNode(8);// Print Levels In Start End FashionprintLevelInStartEndFashion(root);</script> |
Output:
10 13 13 14 15 21 21 22 22 8
Time complexity: The time complexity of this implementation is also O(N), as the printLevel function visits each node in the tree exactly once and performs a constant amount of work for each node.
Auxiliary Space: The Auxiliary Space of this implementation is O(N), where N is the number of nodes in the tree. This is because the printLevel function uses an array of size N to store the nodes at each level of the tree as it performs a level order traversal.
Feeling lost in the world of random DSA topics, wasting time without progress? It’s time for a change! Join our DSA course, where we’ll guide you on an exciting journey to master DSA efficiently and on schedule.
Ready to dive in? Explore our Free Demo Content and join our DSA course, trusted by over 100,000 zambiatek!
Ready to dive in? Explore our Free Demo Content and join our DSA course, trusted by over 100,000 zambiatek!
