Table of contents
1.
Introduction
1.1.
Problem Statement
1.2.
Sample Example
2.
Recursive Approach
2.1.
Pseudocode
2.2.
Implementation in C++
2.3.
Implementation in Python
2.4.
Complexity Analysis
3.
Iterative Approach
3.1.
Pseudocode
3.2.
Implementation in C++
3.3.
Implementation in Python
3.4.
Complexity Analysis
4.
Frequently Asked Questions
4.1.
What is Preorder Traversal?
4.2.
What is the Time Complexity of Preorder Traversal?
4.3.
What is the difference between Inorder, Preorder and Postorder Traversal?
5.
Conclusion
Last Updated: Mar 27, 2024
Medium

Print the node values at odd levels of a Binary tree

Author Akshit Mehra
0 upvote
Career growth poll
Do you think IIT Guwahati certified course can help you in your career?

Introduction

A tree data structure is a hierarchical data structure organized in a tree-like shape. It is made up of a core node, structural nodes, and sub-nodes that are linked together via edges. The roots, branches, and leaves of a tree data structure are all related to one another. Binary Tree: A Binary tree is one in which each node has precisely zero or two children. A perfect binary tree is one in which each node, except leaf nodes, has a degree of two. In this blog, we discuss the problem of printing the nodes at odd levels of a tree. We here consider a binary tree, and the level of the root node is 1. 

Problem Statement

In this blog, we discuss the problem of printing the nodes at odd levels of a binary tree.

Sample Example

                                         

Output: 1 4 5 6 7

Explanation: The above-printed elements correspond to levels one and 3rd, which are odd levels.

Recursive Approach

The first approach involves using recursion. Below is the mentioned algorithm:

  1. We simply do the preorder traversal of the binary tree.
  2. Maintain a variable level. When calling for a successor node, increment the level by 1.
  3. If the level is odd, print the node value.

Pseudocode

Preorder(root, level):
If root is Null:
Return
If level is odd:
print(root->value)
Preorder(root->left, level+1)
Preorder(root->right, level+1)

Implementation in C++

#include "bits/stdc++.h"
using namespace std;

// Class for defining a Tree Node;
class Node{
    public:
    int value;
    Node* left;
    Node* right;
};

// Function to construct a new Node;
Node* NewNode(int val){
    Node* node = new Node;
    node->value = val;
    node->left = NULL;
    node->right = NULL;

    return node;
}

//To check if a leaf node;
bool leaf(Node* root){
    return(!root->left && !root->right);
}

void printOddLevel(Node* root, int level){
    if(!root){
        return;
    }
    // If odd level, print the node value;
    if(level%2){
        cout<<root->value<<" ";
    }
    printOddLevel(root->left, level+1);
    printOddLevel(root->right, level+1);
}
void solve()
{  
    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->right->right->right = NewNode(8);
   
    int level = 1;
    cout<<"Odd level Nodes: ";
    // Function for printing the nodes;
    printOddLevel(root, level);
}  
int main()
{
    solve();
    return 0;
}

Implementation in Python

#Defining the class node
class Node:
    def __init__(self, data):
        self.data = data
        self.left = None
        self.right = None


def PrintOddLevel(root, level):
    if root == None:
        return
    
    #Print if odd level node
    if level%2:
        print(root.data, end = " ")
    
    #Recursive call for left child of root
    PrintOddLevel(root.left, level+1)
    
    #Recursive call for right child of root
    PrintOddLevel(root.right, level+1)


if __name__ == '__main__':
    root = Node(1)
    root.left = Node(2)
    root.right = Node(3)
    root.left.left = Node(4)
    root.left.right = Node(5)
    root.right.left = Node(6)
    root.right.right = Node(7)
    
    #Function For printing odd level nodes
    PrintOddLevel(root, 1)

 

Output:

 1 4 5 6 7 

 

Complexity Analysis

Time complexity: O(n)

Explanation: As we traverse each node once, therefore the Time complexity of the above approach is O(n), where n denotes the number of nodes in the Tree.

Space complexity: O(n)

Explanation: Here, we see the maximum depth of the recursive stack is the corresponding space complexity. Therefore, the space complexity is O(n).

Must Read Recursion in Data Structure

Iterative Approach

A 2nd approach is an Iterative Approach. Here we use queue data structure and perform a Breadth-First Search on the Tree. Below is the algorithm:

  1. Declare a queue of type pair<Node, level>. Insert the root in the queue with level = 1.
  2. If the current level is odd, print the node. 
  3. Run the loop till the queue is empty. Enter the children in the queue with the next level as current level + 1.

Pseudocode

Queue<pair<Node, int>>q;
q.Insert({root, 1}};
While the queue is not empty:
	Node = q.front().first;
	Level = q.front().second;
	q.pop();
	If level is odd:
		Print the value of Node
	If left child of Node exist:
		q.insert(Node->left)
	If right child of Node exist:
		q.insert(Node->right)

Implementation in C++

#include "bits/stdc++.h"
using namespace std;

// Class for defining a Tree Node;
class Node{
    public:
    int value;
    Node* left;
    Node* right;
};

// Function to construct a new Node;
Node* NewNode(int val){
    Node* node = new Node;
    node->value = val;
    node->left = NULL;
    node->right = NULL;

    return node;
}

//To check if a leaf node;
bool leaf(Node* root){
    return(!root->left && !root->right);
}

void printOddLevel(Node* root, int level){
    if(!root){
        return;
    }
    if(level%2){
        cout<<root->value<<" ";
    }
    printOddLevel(root->left, level+1);
    printOddLevel(root->right, level+1);
}
void solve()
{  
    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->right->right->right = NewNode(8);
   
    //Level variable maintaining the level of tree
    int level = 1;
    queue<pair<Node*, int>>q;

    //Pushing the root node with level 1;
    q.push({root, 1});
    while(!q.empty()){

        //Getting the front node;
        Node* node = q.front().first;
        int lvl = q.front().second;
        q.pop();

        //If odd level, print the node value;
        if(lvl%2){
            cout<<node->value<<" ";
        }

        //If left child exist, push the left of the current node;
        if(node->left){
            q.push({node->left,lvl+1});
        }

        //If right node exist, push the right child of the current node;
        if(node->right){
            q.push({node->right, lvl+1});
        }
    }
}  
int main()
{
    solve();
    return 0;
}

Implementation in Python

#Defining the class node
class Node:
    def __init__(self, data):
        self.data = data
        self.left = None
        self.right = None


def PrintOddLevel(root):
    
    #If None node, return;
    if root == None:
        return
    
    #As the root is at odd level, we initialise the odd variable as true;
    odd = True
    
    #Defining a queue
    q = [root]
    
    #While nodes exist
    while(len(q)):
        
        #Getting the number of nodes at current level;
        cnt = len(q)
        #If odd level, we print all the nodes at current level
        if odd:
            while(cnt):
                cnt-=1
                node = q.pop(0)
                print(node.data, end = " ")
                if node.left != None:
                    q.append(node.left)
                
                if node.right != None:
                    q.append(node.right)
        else:
            
            #If even, we just store the children in the queue w/o priting them;
            while(cnt):
                cnt-=1
                node = q.pop(0)
                if node.left != None:
                    q.append(node.left)
                
                if node.right != None:
                    q.append(node.right)
        odd = not odd


if __name__ == '__main__':
    root = Node(1)
    root.left = Node(2)
    root.right = Node(3)
    root.left.left = Node(4)
    root.left.right = Node(5)
    root.right.left = Node(6)
    root.right.right = Node(7)
    
    #Function For printing odd level nodes
    PrintOddLevel(root)

 

Output:

 1 4 5 6 7 

 

Complexity Analysis

Time complexity: O(n)

Explanation: As we traverse each node once, therefore the Time complexity of the above approach is O(n), where n is the number of nodes in the Tree.

Space complexity: O(n)

Explanation:  Here, we use a queue to store the nodes. Therefore, the space complexity is O(n), where n denotes the number of nodes in the Tree.

Frequently Asked Questions

What is Preorder Traversal?

Preorder traversal is a tree traversal where we first process the current node, then we subsequently visit the left node and then the right node.To make a duplicate of the tree, preorder traversal is used. On an expression tree, preorder traversal is also used to get prefix expressions.

What is the Time Complexity of Preorder Traversal?

As we can see in the above algorithm, we see that we visit every node of the Tree only once. Therefore, the time complexity of the PreorderTraversal is O(n), where n is the number of nodes in the Tree.

What is the difference between Inorder, Preorder and Postorder Traversal?

  1. In order, you travel from the left subtree to the root, then to the right subtree.
  2. You go from the root to the left subtree, then to the right subtree for Preorder.
  3. You go from the left subtree to the right subtree, then to the root, in Post order.

Conclusion

In this blog, we discussed the problem of printing the node values at the odd level of a binary tree. Above, we discussed 2 approaches, One was recursive and the other Iterative.Refer to our Guided Path on Coding Ninjas Studio to upskill yourself in Data Structures and AlgorithmsCompetitive ProgrammingJavaScriptSystem DesignMachine learning, and many more! If you want to test your competency in coding, you may check out the mock test series and participate in the contests hosted on Coding Ninjas Studio! But if you have just started your learning process and are looking for questions asked by tech giants like Amazon, Microsoft, Uber, etc., you must look at the problemsinterview experiences, and interview bundle for placement preparations.

Nevertheless, you may consider our paid courses to give your career an edge over others!

Recommended Problems:

Do upvote our blogs if you find them helpful and engaging!

Happy Learning!!

Live masterclass