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 nodestruct Node {Â Â Â Â char key;Â Â Â Â struct Node *left, *right;};Â
// Utility function to create new NodeNode* 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 treevoid inorder(Node* root){Â Â Â Â if (root != NULL) {Â Â Â Â Â Â Â Â inorder(root->left);Â Â Â Â Â Â Â Â cout << root->key << " ";Â Â Â Â Â Â Â Â inorder(root->right);Â Â Â Â }}Â
// Function to reverse alternate nodesvoid 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 codeint 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 nodeclass Node:         def __init__(self, key):               self.key = key        self.left = None        self.right = None     # Utility function to# create new Nodedef newNode(key):Â
    temp = Node(key)    return tempÂ
# Utility function to perform# inorder traversal of the treedef inorder(root):Â
    if (root != None):        inorder(root.left);        print(root.key,              end = ' ')        inorder(root.right);   Â
# Function to reverse # alternate nodesdef 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 codeif __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> |
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.
Ready to dive in? Explore our Free Demo Content and join our DSA course, trusted by over 100,000 neveropen!

… [Trackback]
[…] Information on that Topic: geeksforgeeks.org/reverse-alternate-levels-of-a-perfect-binary-tree-using-stack/ […]
… [Trackback]
[…] There you can find 20673 more Info to that Topic: geeksforgeeks.org/reverse-alternate-levels-of-a-perfect-binary-tree-using-stack/ […]