Code360 powered by Coding Ninjas X Naukri.com. Code360 powered by Coding Ninjas X Naukri.com
Table of contents
1.
Introduction
2.
Example
2.1.
Input
2.2.
Output
3.
Algorithm
3.1.
C++ Code
3.2.
Java Code
3.3.
Input
3.4.
Output
4.
Complexities
4.1.
Time complexity 
4.2.
Space complexity
5.
Frequently Asked Questions
5.1.
What are binary trees, and how do they work?
5.2.
Is it possible for a binary search tree to have duplicates?
5.3.
What is the purpose of binary trees?
5.4.
What are the different types of Binary Trees?
5.5.
What is the best way to find the preOrder traversal?
6.
Conclusion
Last Updated: Mar 27, 2024

Perfect Binary Tree Specific Level Order Traversal

Author Manan Singhal
0 upvote
Roadmap to SDE career at Amazon
Speaker
Anubhav Sinha
SDE-2 @
25 Jun, 2024 @ 01:30 PM

Introduction

Nodes should be printed in level order but alternately from the left and right sides. According to the below example, the first and second levels are easy while the third level is printed: 4(left), 7(right), 5(left), and 6(right), and the fourth level is printed as 8(left), 15(right), 9(left), 14(right), and so on.

Example

Input

Output

1 2 3 4 7 5 6 8 15 8 14 10 13 11 12
Get the tech career you deserve, faster!
Connect with our expert counsellors to understand how to hack your way to success
User rating 4.7/5
1:1 doubt support
95% placement record
Akash Pal
Senior Software Engineer
326% Hike After Job Bootcamp
Himanshu Gusain
Programmer Analyst
32 LPA After Job Bootcamp
After Job
Bootcamp

Algorithm

The standard level order traversal concept will be slightly altered in this case. We will process TWO nodes simultaneously rather than processing one node at a time. The enqueue order will be: 1st node's left child, 2nd node's right child, 1st node's right child, and 2nd node's left child when pushing children into the queue.

C++ Code

/* C++ program to print perfect binary tree specific level order traversal */

#include <iostream>
#include <queue>

using namespace std;

/* The left and right children of the current Node and the key-value are contained in this class. */
struct Node
{
	int data;
	Node *left;
	Node *right;
};

Node *newNode(int data)
{
	Node *node = new Node;
	node->data = data;
	node->right = node->left = NULL;
	return node;
}

/* Print the nodes of a perfect binary tree in given level order. */
void printSpecificLevelOrder(Node *root)
{
	if (root == NULL)
		return;

	/* Let's start with the root and next level. */
	cout << root->data;

	/* Right is not checked because it is a perfect Binary Tree. */
	if (root->left != NULL)
    	cout << " " << root->left->data << " " << root->right->data;

	/* If there are nodes at the following level in the specified perfect Binary Tree, do anything else. */
	if (root->left->left == NULL)
		return;

	/* Make a queue and add root's left and right children to it. */
	queue <Node *> q;
	q.push(root->left);
	q.push(root->right);

	/* Because we process two nodes at once, we require two variables to store the two front items of the queue. */
	Node *first = NULL, *second = NULL;

	while (!q.empty())
	{
     	/* Pop items from queue */
     	first = q.front();
     	q.pop();
     	second = q.front();
     	q.pop();
    	
     	cout << " " << first->left->data << " " << second->right->data;
     	cout << " " << first->right->data << " " << second->left->data;
     	
     	if (first->left->left != NULL)
     	{
     	q.push(first->left);
     	q.push(second->right);
     	q.push(first->right);
     	q.push(second->left);
     	}
	}
}

/* Main Program */
int main()
{
	/* Binary tree creation */
	Node *root = newNode(1);

	root->left = newNode(2);
	root->right = newNode(3);

	root->left->left = newNode(4);
	root->left->right = newNode(5);
	root->right->left = newNode(6);
	root->right->right = newNode(7);

	root->left->left->left = newNode(8);
	root->left->left->right = newNode(9);
	root->left->right->left = newNode(10);
	root->left->right->right = newNode(11);
	root->right->left->left = newNode(12);
	root->right->left->right = newNode(13);
	root->right->right->left = newNode(14);
	root->right->right->right = newNode(15);

	printSpecificLevelOrder(root);

	return 0;
}

Java Code

/* Java program to print perfect binary tree specific level order traversal */

import java.util.LinkedList;
import java.util.Queue;

/* The left and right children of the current Node and the key-value are contained in this class. */
class Node
{
	int data;
	Node left, right;

	public Node (int item)
	{
		data = item;
		left = right = null;
	}
}

class Main
{
	Node root;

	/* Print the nodes of a perfect binary tree in given level order. */
	void printSpecificLevelOrder(Node node)
	{
		if (node == null)
			return;

		/* Let's start with the root and next level. */
		System.out.print(node.data);

		/* Right is not checked because it is a perfect Binary Tree. */
		if (node.left != null)
			System.out.print(" " + node.left.data + " " + node.right.data);

		/* If there are nodes at the following level in the specified perfect Binary Tree, do anything else. */
		if (node.left.left == null)
			return;

		/* Make a queue and add root's left and right children to it. */
		Queue<Node> q = new LinkedList<Node>();
		q.add(node.left);
		q.add(node.right);

		/* Because we process two nodes at once, we require two variables to store the two front items of the queue. */
		Node first = null, second = null;

		while (!q.isEmpty())
		{
			/* Pop items from queue */
			first = q.peek();
			q.remove();
			second = q.peek();
			q.remove();

			System.out.print(" " + first.left.data + " " +second.right.data);
			System.out.print(" " + first.right.data + " " +second.left.data);

			if (first.left.left != null)
			{
				q.add(first.left);
				q.add(second.right);
				q.add(first.right);
				q.add(second.left);
			}
		}
	}

	/* Main Program */
	public static void main(String args[])
	{
    	/* Binary tree creation */
		Main tree = new Main();
		tree.root = new Node(1);
		tree.root.left = new Node(2);
		tree.root.right = new Node(3);

		tree.root.left.left = new Node(4);
		tree.root.left.right = new Node(5);
		tree.root.right.left = new Node(6);
		tree.root.right.right = new Node(7);

		tree.root.left.left.left = new Node(8);
		tree.root.left.left.right = new Node(9);
		tree.root.left.right.left = new Node(10);
		tree.root.left.right.right = new Node(11);
		tree.root.right.left.left = new Node(12);
		tree.root.right.left.right = new Node(13);
		tree.root.right.right.left = new Node(14);
		tree.root.right.right.right = new Node(15);

		tree.printSpecificLevelOrder(tree.root);
	}
}

Input

Output

1 2 3 4 7 5 6 8 15 8 14 10 13 11 12

Complexities

Time complexity 

O(n),
Reason: When executing level order traversal, each node is explored at once so that the time complexity will be O(n).

Space complexity

O(1),
Reason: No extra space required.

Check out this problem - Mirror A Binary Tree

Frequently Asked Questions

What are binary trees, and how do they work?

It is a non-linear data structure of the tree type with a maximum of two offspring per parent. The root node is the node at the very top of a tree's hierarchy. The parent nodes are the nodes that include additional sub-nodes.

Is it possible for a binary search tree to have duplicates?

No, because a search tree has no advantage in allowing duplicates because searching for one value in a binary search tree can only provide one value, not two or more.

What is the purpose of binary trees?

Binary trees are mostly used in computing for searching and sorting since they allow data to be stored hierarchically. Insertion, deletion, and traversal are some of the most frequent operations performed on binary trees.

What are the different types of Binary Trees?

Following are the different types of binary trees: full binary tree, perfect binary tree, skewed binary tree, complete binary tree, and degenerate binary tree.

What is the best way to find the preOrder traversal?

We can use the preOrder traversal's recursive definition to visit the root, recursively travel to the left subtree, and then proceed to the right subtree.

Conclusion

In this article, we have printed the perfect binary tree-specific level order traversal. We hope this blog will help you understand the concept of a binary tree, and if you want to learn more about the binary tree, check out our other blogs on the binary treean introduction to binary tree, and binary search tree.

Recommended problems -

 

Refer to our guided paths on Coding Ninjas Studio to learn about Data Structure and Algorithms, Competitive Programming, JavaScript, etc. Enroll in our courses and refer to our mock test available. Have a look at the interview experiences and interview bundle for placement preparations.

Happy Coding!

Previous article
Replace Every Node of an N-ary Tree with the Sum of all its Subtrees
Next article
Construct an Ancestor Matrix from the given Binary Tree
Live masterclass