Reverse alternate levels of a perfect binary tree using Stack

0 0 8 minutes read

Given a Perfect Binary Tree, the task is to reverse the alternate level nodes of the binary tree.
Examples:

Input:
               a
            /     \
           b       c
         /  \     /  \
        d    e    f    g
       / \  / \  / \  / \
       h  i j  k l  m  n  o  
Output:
Inorder Traversal of given tree
h d i b j e k a l f m c n g o 
Inorder Traversal of modified tree
o d n c m e l a k f j b i g h

Input:
               a
              / \
             b   c
Output:
Inorder Traversal of given tree
b a c 
Inorder Traversal of modified tree
c a b

Approach: Another approach to the problem is discussed here. In this article, we discuss an approach involving stack.
Traverse the tree in a depth-first fashion and for each level,

If the level is odd, push the left and right child(if exists) in a stack.
If the level is even, replace the value of the current node with the top of the stack.

Below is the implementation of the above approach:

C++

// C++ implementation of the approach
#include <bits/stdc++.h>
using namespace std;
 
// A tree node
struct Node {
    char key;
    struct Node *left, *right;
};
 
// Utility function to create new Node
Node* newNode(int key)
{
    Node* temp = new Node;
    temp->key = key;
    temp->left = temp->right = NULL;
    return (temp);
}
 
// Utility function to perform
// inorder traversal of the tree
void inorder(Node* root)
{
    if (root != NULL) {
        inorder(root->left);
        cout << root->key << " ";
        inorder(root->right);
    }
}
 
// Function to reverse alternate nodes
void reverseAlternate(Node* root)
{
 
    // Queue for depth first traversal
    queue<Node*> q;
    q.push(root);
    Node* temp;
 
    // Level of root considered to be 1
    int n, level = 1;
 
    // Stack to store nodes of a level
    stack<int> s;
 
    while (!q.empty()) {
        n = q.size();
        while (n--) {
            temp = q.front();
            q.pop();
 
            // If level is odd
            if (level % 2) {
 
                // Store the left and right child
                // in the stack
                if (temp->left) {
                    q.push(temp->left);
                    s.push(temp->left->key);
                }
 
                if (temp->right) {
                    q.push(temp->right);
                    s.push(temp->right->key);
                }
            }
 
            // If level is even
            else {
 
                // Replace the value of node
                // with top of the stack
                temp->key = s.top();
                s.pop();
 
                if (temp->left)
                    q.push(temp->left);
                if (temp->right)
                    q.push(temp->right);
            }
        }
 
        // Increment the level
        level++;
    }
}
 
// Driver code
int main()
{
    struct Node* root = newNode('a');
    root->left = newNode('b');
    root->right = newNode('c');
    root->left->left = newNode('d');
    root->left->right = newNode('e');
    root->right->left = newNode('f');
    root->right->right = newNode('g');
    root->left->left->left = newNode('h');
    root->left->left->right = newNode('i');
    root->left->right->left = newNode('j');
    root->left->right->right = newNode('k');
    root->right->left->left = newNode('l');
    root->right->left->right = newNode('m');
    root->right->right->left = newNode('n');
    root->right->right->right = newNode('o');
 
    cout << "Inorder Traversal of given tree\n";
    inorder(root);
 
    reverseAlternate(root);
 
    cout << "\nInorder Traversal of modified tree\n";
    inorder(root);
 
    return 0;
}

Java

// Java implementation of the approach 
import java.util.*;
 
class GfG
{ 
 
// A tree node 
static class Node
{ 
    char key; 
    Node left, right; 
}
 
// Utility function to create new Node 
static Node newNode(char key) 
{ 
    Node temp = new Node(); 
    temp.key = key; 
    temp.left = temp.right = null; 
    return (temp); 
} 
 
// Utility function to perform 
// inorder traversal of the tree 
static void inorder(Node root) 
{ 
    if (root != null)
    { 
        inorder(root.left); 
        System.out.print(root.key + " "); 
        inorder(root.right); 
    } 
} 
 
// Function to reverse alternate nodes 
static void reverseAlternate(Node root) 
{ 
 
    // Queue for depth first traversal 
    Queue<Node> q = new LinkedList<Node> (); 
    q.add(root); 
    Node temp; 
 
    // Level of root considered to be 1 
    int n, level = 1; 
 
    // Stack to store nodes of a level 
    Stack<Character> s = new Stack<Character> (); 
 
    while (!q.isEmpty())
    { 
        n = q.size(); 
        while (n != 0)
        { 
            if(!q.isEmpty()) 
            {
                temp = q.peek(); 
                q.remove(); 
            }
            else
            temp = null;
             
            // If level is odd 
            if (level % 2 != 0)
            { 
 
                // Store the left and right child 
                // in the stack 
                if (temp != null && temp.left != null) 
                { 
                    q.add(temp.left); 
                    s.push(temp.left.key); 
                } 
 
                if (temp != null && temp.right != null)
                { 
                    q.add(temp.right); 
                    s.push(temp.right.key); 
                } 
            } 
 
            // If level is even 
            else
            { 
 
                // Replace the value of node 
                // with top of the stack 
                temp.key = s.peek(); 
                s.pop(); 
 
                if (temp.left != null) 
                    q.add(temp.left); 
                if (temp.right != null) 
                    q.add(temp.right); 
            }
            n--;
        } 
 
        // Increment the level 
        level++; 
    } 
} 
 
// Driver code 
public static void main(String[] args) 
{ 
    Node root = newNode('a'); 
    root.left = newNode('b'); 
    root.right = newNode('c'); 
    root.left.left = newNode('d'); 
    root.left.right = newNode('e'); 
    root.right.left = newNode('f'); 
    root.right.right = newNode('g'); 
    root.left.left.left = newNode('h'); 
    root.left.left.right = newNode('i'); 
    root.left.right.left = newNode('j'); 
    root.left.right.right = newNode('k'); 
    root.right.left.left = newNode('l'); 
    root.right.left.right = newNode('m'); 
    root.right.right.left = newNode('n'); 
    root.right.right.right = newNode('o'); 
 
    System.out.println("Inorder Traversal of given tree"); 
    inorder(root); 
 
    reverseAlternate(root); 
 
    System.out.println("\nInorder Traversal of modified tree"); 
    inorder(root); 
}
} 
 
// This code is contributed by Prerna Saini

Python3

# Python3 implementation of the 
# above approach
 
# A tree node
class Node:
     
    def __init__(self, key):
       
        self.key = key
        self.left = None
        self.right = None
     
# Utility function to
# create new Node
def newNode(key):
 
    temp = Node(key)
    return temp
 
# Utility function to perform
# inorder traversal of the tree
def inorder(root):
 
    if (root != None):
        inorder(root.left);
        print(root.key,
              end = ' ')
        inorder(root.right);    
 
# Function to reverse 
# alternate nodes
def reverseAlternate(root):
  
    # Queue for depth 
    # first traversal
    q = []
    q.append(root);
     
    temp = None
  
    # Level of root considered 
    # to be 1
    n = 0
    level = 1;
  
    # Stack to store nodes 
    # of a level
    s = []
  
    while (len(q) != 0):        
        n = len(q);        
        while (n != 0):            
            n -= 1
            temp = q[0];
            q.pop(0);
  
            # If level is odd
            if (level % 2 != 0):
  
                # Store the left and 
                # right child in the stack
                if (temp.left != None):
                    q.append(temp.left);
                    s.append(temp.left.key);
                 
  
                if (temp.right != None):
                    q.append(temp.right);
                    s.append(temp.right.key);
  
            # If level is even
            else:
  
                # Replace the value of node
                # with top of the stack
                temp.key = s[-1];
                s.pop();
  
                if (temp.left != None):
                    q.append(temp.left);
                if (temp.right != None):
                    q.append(temp.right);
  
        # Increment the level
        level += 1;    
 
# Driver code
if __name__ == "__main__":
     
    root = newNode('a');
    root.left = newNode('b');
    root.right = newNode('c');
    root.left.left = newNode('d');
    root.left.right = newNode('e');
    root.right.left = newNode('f');
    root.right.right = newNode('g');
    root.left.left.left = newNode('h');
    root.left.left.right = newNode('i');
    root.left.right.left = newNode('j');
    root.left.right.right = newNode('k');
    root.right.left.left = newNode('l');
    root.right.left.right = newNode('m');
    root.right.right.left = newNode('n');
    root.right.right.right = newNode('o');
     
    print("Inorder Traversal of given tree")
    inorder(root);
  
    reverseAlternate(root);
     
    print("\nInorder Traversal of modified tree")
    inorder(root);
     
# This code is contributed by Rutvik_56

C#

// C# implementation of the approach 
using System;
using System.Collections;
 
class GfG 
{ 
 
// A tree node 
public class Node 
{ 
    public char key; 
    public Node left, right; 
} 
 
// Utility function to create new Node 
static Node newNode(char key) 
{ 
    Node temp = new Node(); 
    temp.key = key; 
    temp.left = temp.right = null; 
    return (temp); 
} 
 
// Utility function to perform 
// inorder traversal of the tree 
static void inorder(Node root) 
{ 
    if (root != null) 
    { 
        inorder(root.left); 
        Console.Write(root.key + " "); 
        inorder(root.right); 
    } 
} 
 
// Function to reverse alternate nodes 
static void reverseAlternate(Node root) 
{ 
 
    // Queue for depth first traversal 
    Queue q = new Queue (); 
    q.Enqueue(root); 
    Node temp; 
 
    // Level of root considered to be 1 
    int n, level = 1; 
 
    // Stack to store nodes of a level 
    Stack s = new Stack (); 
 
    while (q.Count > 0) 
    { 
        n = q.Count; 
        while (n != 0) 
        { 
            if(q.Count > 0) 
            { 
                temp = (Node)q.Peek(); 
                q.Dequeue(); 
            } 
            else
            temp = null; 
             
            // If level is odd 
            if (level % 2 != 0) 
            { 
 
                // Store the left and right child 
                // in the stack 
                if (temp != null && temp.left != null) 
                { 
                    q.Enqueue(temp.left); 
                    s.Push(temp.left.key); 
                } 
 
                if (temp != null && temp.right != null) 
                { 
                    q.Enqueue(temp.right); 
                    s.Push(temp.right.key); 
                } 
            } 
 
            // If level is even 
            else
            { 
 
                // Replace the value of node 
                // with top of the stack 
                temp.key =(char)s.Peek(); 
                s.Pop(); 
 
                if (temp.left != null) 
                    q.Enqueue(temp.left); 
                if (temp.right != null) 
                    q.Enqueue(temp.right); 
            } 
            n--; 
        } 
 
        // Increment the level 
        level++; 
    } 
} 
 
// Driver code 
public static void Main(String []args) 
{ 
    Node root = newNode('a'); 
    root.left = newNode('b'); 
    root.right = newNode('c'); 
    root.left.left = newNode('d'); 
    root.left.right = newNode('e'); 
    root.right.left = newNode('f'); 
    root.right.right = newNode('g'); 
    root.left.left.left = newNode('h'); 
    root.left.left.right = newNode('i'); 
    root.left.right.left = newNode('j'); 
    root.left.right.right = newNode('k'); 
    root.right.left.left = newNode('l'); 
    root.right.left.right = newNode('m'); 
    root.right.right.left = newNode('n'); 
    root.right.right.right = newNode('o'); 
 
    Console.WriteLine("Inorder Traversal of given tree"); 
    inorder(root); 
 
    reverseAlternate(root); 
 
    Console.WriteLine("\nInorder Traversal of modified tree"); 
    inorder(root); 
} 
} 
 
// This code is contributed by Arnab Kundu

Javascript

<script>
 
// JavaScript implementation of the approach 
 
// A tree node 
class Node 
{ 
    constructor()
    {
        this.key = '';
        this.left = null;
        this.right = null;
    }
} 
 
// Utility function to create new Node 
function newNode(key) 
{ 
    var temp = new Node(); 
    temp.key = key; 
    temp.left = temp.right = null; 
    return (temp); 
} 
 
// Utility function to perform 
// inorder traversal of the tree 
function inorder(root) 
{ 
    if (root != null) 
    { 
        inorder(root.left); 
        document.write(root.key + " "); 
        inorder(root.right); 
    } 
} 
 
// Function to reverse alternate nodes 
function reverseAlternate(root) 
{ 
 
    // Queue for depth first traversal 
    var q = []; 
    q.push(root); 
    var temp = null; 
 
    // Level of root considered to be 1 
    var n, level = 1; 
 
    // Stack to store nodes of a level 
    var s = [];
 
    while (q.length > 0) 
    { 
        n = q.length; 
        while (n != 0) 
        { 
            if(q.length > 0) 
            { 
                temp = q[0]; 
                q.shift(); 
            } 
            else
            temp = null; 
             
            // If level is odd 
            if (level % 2 != 0) 
            { 
 
                // Store the left and right child 
                // in the stack 
                if (temp != null && temp.left != null) 
                { 
                    q.push(temp.left); 
                    s.push(temp.left.key); 
                } 
 
                if (temp != null && temp.right != null) 
                { 
                    q.push(temp.right); 
                    s.push(temp.right.key); 
                } 
            } 
 
            // If level is even 
            else
            { 
 
                // Replace the value of node 
                // with top of the stack 
                temp.key = s[s.length-1]; 
                s.pop(); 
 
                if (temp.left != null) 
                    q.push(temp.left); 
                if (temp.right != null) 
                    q.push(temp.right); 
            } 
            n--; 
        } 
 
        // Increment the level 
        level++; 
    } 
} 
 
// Driver code 
var root = newNode('a'); 
root.left = newNode('b'); 
root.right = newNode('c'); 
root.left.left = newNode('d'); 
root.left.right = newNode('e'); 
root.right.left = newNode('f'); 
root.right.right = newNode('g'); 
root.left.left.left = newNode('h'); 
root.left.left.right = newNode('i'); 
root.left.right.left = newNode('j'); 
root.left.right.right = newNode('k'); 
root.right.left.left = newNode('l'); 
root.right.left.right = newNode('m'); 
root.right.right.left = newNode('n'); 
root.right.right.right = newNode('o'); 
document.write("Inorder Traversal of given tree<br>"); 
inorder(root); 
reverseAlternate(root); 
document.write("<br>Inorder Traversal of modified tree<br>"); 
inorder(root); 
 
</script>

Output:

Inorder Traversal of given tree
h d i b j e k a l f m c n g o 
Inorder Traversal of modified tree
o d n c m e l a k f j b i g h

The time complexity of the above approach is O(N) where N is the number of nodes in the tree as we are traversing through all the nodes once.

The space complexity of the above approach is O(N) as we are using a queue and a stack which can store up to N elements.

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!