Given a binary tree, the task is to traverse each level of the given binary tree from left to right and print every alternate encountered at a level.
Examples:
Input:
Output:
1
2
3 9
5 7Input:
Output:
71
88
4 6
8 10 13
Approach: The problem can be solved by performing Level Order Traversal traversal on the given binary tree. Follow the steps below to solve the problem:
- Initialize a Queue, to store the nodes of each level of the given binary tree.
- Perform level order traversal and print alternate nodes from each level of the Binary Tree
Below is the implementation of the above approach:
C++
// C++ program to implement// the above approach#include <bits/stdc++.h>using namespace std;// Structure of a Nodestruct Node { int data; Node* left; Node* right; Node(int val) { data = val; left = right = NULL; }};// Print alternate nodes of// a binary treevoid PrintAlternate(Node* root){ // Store nodes of each level queue<Node*> Q; Q.push(root); while (!Q.empty()) { // Store count of nodes // of current level int N = Q.size(); // Print alternate nodes of // the current level for (int i = 0; i < N; i++) { Node* temp = Q.front(); Q.pop(); if (i % 2 == 0) { cout << temp->data << " "; } // If left child exists if (temp->left) { // Store left child Q.push(temp->left); } // If right child exists if (temp->right) { // Store right child Q.push(temp->right); } } cout << endl; }}// Driver Codeint main(){ Node* root; // Create a tree root = new Node(71); root->left = new Node(88); root->right = new Node(99); root->left->left = new Node(4); root->left->right = new Node(5); root->right->left = new Node(6); root->right->right = new Node(7); root->left->left->left = new Node(8); root->left->left->right = new Node(9); root->left->right->left = new Node(10); root->left->right->right = new Node(11); root->right->left->right = new Node(13); root->right->right->left = new Node(14); PrintAlternate(root);} |
Java
// Java program to implement// the above approachimport java.util.*;class GFG{// Structure of a Nodestatic class Node { int data; Node left; Node right; Node(int val) { data = val; left = right = null; }};// Print alternate nodes of// a binary treestatic void PrintAlternate(Node root){ // Store nodes of each level Queue<Node> Q = new LinkedList<>(); Q.add(root); while (!Q.isEmpty()) { // Store count of nodes // of current level int N = Q.size(); // Print alternate nodes of // the current level for (int i = 0; i < N; i++) { Node temp = Q.peek(); Q.remove(); if (i % 2 == 0) { System.out.print(temp.data + " "); } // If left child exists if (temp.left!=null) { // Store left child Q.add(temp.left); } // If right child exists if (temp.right!=null) { // Store right child Q.add(temp.right); } } System.out.println(); }}// Driver Codepublic static void main(String[] args){ Node root; // Create a tree root = new Node(71); root.left = new Node(88); root.right = new Node(99); root.left.left = new Node(4); root.left.right = new Node(5); root.right.left = new Node(6); root.right.right = new Node(7); root.left.left.left = new Node(8); root.left.left.right = new Node(9); root.left.right.left = new Node(10); root.left.right.right = new Node(11); root.right.left.right = new Node(13); root.right.right.left = new Node(14); PrintAlternate(root);}}// This code is contributed by 29AjayKumar |
Python3
# Python3 program to implement# the above approach# Structure of a Nodeclass newNode: def __init__(self, val): self.data = val self.left = None self.right = None# Print alternate nodes of# a binary treedef PrintAlternate(root): # Store nodes of each level Q = [] Q.append(root) while (len(Q)): # Store count of nodes # of current level N = len(Q) # Print alternate nodes of # the current level for i in range(N): temp = Q[0] Q.remove(Q[0]) if (i % 2 == 0): print(temp.data, end = " ") # If left child exists if (temp.left): # Store left child Q.append(temp.left) # If right child exists if (temp.right): # Store right child Q.append(temp.right) print("\n", end = "")# Driver Codeif __name__ == '__main__': # Create a tree root = newNode(71) root.left = newNode(88) root.right = newNode(99) 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.right = newNode(13) root.right.right.left = newNode(14) PrintAlternate(root)# This code is contributed by ipg2016107 |
C#
// C# program to implement// the above approachusing System;using System.Collections.Generic;class GFG{// Structure of a Nodeclass Node { public int data; public Node left; public Node right; public Node(int val) { data = val; left = right = null; }};// Print alternate nodes of// a binary treestatic void PrintAlternate(Node root){ // Store nodes of each level Queue<Node> Q = new Queue<Node>(); Q.Enqueue(root); while (Q.Count != 0) { // Store count of nodes // of current level int N = Q.Count; // Print alternate nodes of // the current level for (int i = 0; i < N; i++) { Node temp = Q.Peek(); Q.Dequeue(); if (i % 2 == 0) { Console.Write(temp.data + " "); } // If left child exists if (temp.left!=null) { // Store left child Q.Enqueue(temp.left); } // If right child exists if (temp.right!=null) { // Store right child Q.Enqueue(temp.right); } } Console.WriteLine(); }}// Driver Codepublic static void Main(String[] args){ Node root; // Create a tree root = new Node(71); root.left = new Node(88); root.right = new Node(99); root.left.left = new Node(4); root.left.right = new Node(5); root.right.left = new Node(6); root.right.right = new Node(7); root.left.left.left = new Node(8); root.left.left.right = new Node(9); root.left.right.left = new Node(10); root.left.right.right = new Node(11); root.right.left.right = new Node(13); root.right.right.left = new Node(14); PrintAlternate(root);}}// This code is contributed by 29AjayKumar |
Javascript
<script> // Javascript program for the above approach // Structure of a Node class Node { constructor(val) { this.left = null; this.right = null; this.data = val; } } // Print alternate nodes of // a binary tree function PrintAlternate(root) { // Store nodes of each level let Q = []; Q.push(root); while (Q.length > 0) { // Store count of nodes // of current level let N = Q.length; // Print alternate nodes of // the current level for (let i = 0; i < N; i++) { let temp = Q[0]; Q.shift(); if (i % 2 == 0) { document.write(temp.data + " "); } // If left child exists if (temp.left!=null) { // Store left child Q.push(temp.left); } // If right child exists if (temp.right!=null) { // Store right child Q.push(temp.right); } } document.write("</br>"); } } let root; // Create a tree root = new Node(71); root.left = new Node(88); root.right = new Node(99); root.left.left = new Node(4); root.left.right = new Node(5); root.right.left = new Node(6); root.right.right = new Node(7); root.left.left.left = new Node(8); root.left.left.right = new Node(9); root.left.right.left = new Node(10); root.left.right.right = new Node(11); root.right.left.right = new Node(13); root.right.right.left = new Node(14); PrintAlternate(root);</script> |
Output:
71 88 4 6 8 10 13
Time Complexity: O(N)
Auxiliary Space: O(N)
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 neveropen!
Ready to dive in? Explore our Free Demo Content and join our DSA course, trusted by over 100,000 neveropen!
