Tutorialspoint.dev

Perfect Binary Tree Specific Level Order Traversal | Set 2

Perfect Binary Tree using Specific Level Order Traversal in Set 1. The earlier traversal was from Top to Bottom. In this post, Bottom to Top traversal (asked in Amazon Interview | Set 120 – Round 1) is discussed.

image(4)

16 31 17 30 18 29 19 28 20 27 21 26 22 25 23 24 8 15 9 14 10 13 11 12 4 7 5 6 2 3 1



The task is to print nodes in level order but nodes should be from left and right side alternatively and from bottom – up manner

5th level: 16(left), 31(right), 17(left), 30(right), … are printed.

4th level: 8(left), 15(right), 9(left), 14(right), … are printed.

3rd level: 4(left), 7(right), 5(left), 6(right) are printed.

1st and 2nd levels are trivial.

Approach 1
The standard level order traversal idea slightly changes here.

  1. Instead of processing ONE node at a time, we will process TWO nodes at a time.
  2. For dequeued nodes, we push node’s left and right child into stack in following manner – 2nd node’s left child, 1st node’s right child, 2nd node’s right child and 1st node’s left child.
  3. And while pushing children into queue, the enqueue order will be: 1st node’s right child, 2nd node’s left child, 1st node’s left child and 2nd node’s right child. Also, when we process two queue nodes.
  4. Finally pop all Nodes from stack and prints them.

C++

/* C++ program for special order traversal */
#include <bits/stdc++.h>
using namespace std;
  
/* A binary tree node has data, pointer to left child
and a pointer to right child */
struct Node
{
    int data;
    Node *left, *right;
};
  
/* Helper function that allocates a new node with the
given data and NULL left and right pointers. */
Node* newNode(int data)
{
    Node* node = new Node;
    node->data = data;
    node->right = node->left = NULL;
    return node;
}
  
void printSpecificLevelOrderUtil(Node* root, stack<Node*> &s)
{
    if (root == NULL)
        return;
  
    // Create a queue and enqueue left and right
    // children of root
    queue<Node*> q;
  
    q.push(root->left);
    q.push(root->right);
  
    // We process two nodes at a time, so we
    // need two variables to store two front
    // items of queue
    Node *first = NULL, *second = NULL;
  
    // traversal loop
    while (!q.empty())
    {
        // Pop two items from queue
        first = q.front();
        q.pop();
        second = q.front();
        q.pop();
  
        // Push first and second node's chilren
        // in reverse order
        s.push(second->left);
        s.push(first->right);
        s.push(second->right);
        s.push(first->left);
  
        // If first and second have grandchildren,
        // enqueue them in specific order
        if (first->left->left != NULL)
        {
            q.push(first->right);
            q.push(second->left);
            q.push(first->left);
            q.push(second->right);
        }
    }
}
  
/* Given a perfect binary tree, print its nodes in
specific level order */
void printSpecificLevelOrder(Node* root)
{
    //create a stack and push root
    stack<Node*> s;
  
    //Push level 1 and level 2 nodes in stack
    s.push(root);
  
    // Since it is perfect Binary Tree, right is
    // not checked
    if (root->left != NULL)
    {
        s.push(root->right);
        s.push(root->left);
    }
  
    // Do anything more if there are nodes at next
    // level in given perfect Binary Tree
    if (root->left->left != NULL)
        printSpecificLevelOrderUtil(root, s);
  
    // Finally pop all Nodes from stack and prints
    // them.
    while (!s.empty())
    {
        cout << s.top()->data << " ";
        s.pop();
    }
}
  
/* Driver program to test above functions*/
int main()
{
    // Perfect Binary Tree of Height 4
    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);
  
    root->left->left->left->left  = newNode(16);
    root->left->left->left->right  = newNode(17);
    root->left->left->right->left  = newNode(18);
    root->left->left->right->right  = newNode(19);
    root->left->right->left->left  = newNode(20);
    root->left->right->left->right  = newNode(21);
    root->left->right->right->left  = newNode(22);
    root->left->right->right->right  = newNode(23);
    root->right->left->left->left  = newNode(24);
    root->right->left->left->right  = newNode(25);
    root->right->left->right->left  = newNode(26);
    root->right->left->right->right  = newNode(27);
    root->right->right->left->left  = newNode(28);
    root->right->right->left->right  = newNode(29);
    root->right->right->right->left  = newNode(30);
    root->right->right->right->right  = newNode(31);
    */
    cout << "Specific Level Order traversal of binary "
         "tree is ";
    printSpecificLevelOrder(root);
  
    return 0;
}

Java

// Java program for special order traversal
  
import java.util.*;
  
/* A binary tree node has data, pointer to left child
   and a pointer to right child */
class Node 
{
    int data;
    Node left, right;
  
    public Node(int data) 
    {
        this.data = data;
        left = right = null;
    }
}
  
class BinaryTree 
{
    Node root;
  
    void printSpecificLevelOrderUtil(Node root, Stack<Node> s) 
    {
        if (root == null)
            return;
  
        // Create a queue and enqueue left and right
        // children of root
        Queue<Node> q = new LinkedList<Node>();
  
        q.add(root.left);
        q.add(root.right);
  
        // We process two nodes at a time, so we
        // need two variables to store two front
        // items of queue
        Node first = null, second = null;
  
        // traversal loop
        while (!q.isEmpty()) 
        {
            // Pop two items from queue
            first = q.peek();
            q.poll();
            second = q.peek();
            q.poll();
  
            // Push first and second node's chilren
            // in reverse order
            s.push(second.left);
            s.push(first.right);
            s.push(second.right);
            s.push(first.left);
  
            // If first and second have grandchildren,
            // enqueue them in specific order
            if (first.left.left != null) 
            {
                q.add(first.right);
                q.add(second.left);
                q.add(first.left);
                q.add(second.right);
            }
        }
    }
  
    /* Given a perfect binary tree, print its nodes in
       specific level order */
    void printSpecificLevelOrder(Node root) 
    {
        //create a stack and push root
        Stack<Node> s = new Stack<Node>();
  
        //Push level 1 and level 2 nodes in stack
        s.push(root);
  
        // Since it is perfect Binary Tree, right is
        // not checked
        if (root.left != null) 
        {
            s.push(root.right);
            s.push(root.left);
        }
  
        // Do anything more if there are nodes at next
        // level in given perfect Binary Tree
        if (root.left.left != null)
            printSpecificLevelOrderUtil(root, s);
  
        // Finally pop all Nodes from stack and prints
        // them.
        while (!s.empty()) 
        {
            System.out.print(s.peek().data + " ");
            s.pop();
        }
    }
  
    // Driver program to test the above functions
    public static void main(String[] args) 
    {
        BinaryTree tree = new BinaryTree();
        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.root.left.left.left.left  = new Node(16);
        tree.root.left.left.left.right  = new Node(17);
        tree.root.left.left.right.left  = new Node(18);
        tree.root.left.left.right.right  = new Node(19);
        tree.root.left.right.left.left  = new Node(20);
        tree.root.left.right.left.right  = new Node(21);
        tree.root.left.right.right.left  = new Node(22);
        tree.root.left.right.right.right  = new Node(23);
        tree.root.right.left.left.left  = new Node(24);
        tree.root.right.left.left.right  = new Node(25);
        tree.root.right.left.right.left  = new Node(26);
        tree.root.right.left.right.right  = new Node(27);
        tree.root.right.right.left.left  = new Node(28);
        tree.root.right.right.left.right  = new Node(29);
        tree.root.right.right.right.left  = new Node(30);
        tree.root.right.right.right.right  = new Node(31);
         */
        System.out.println("Specific Level Order Traversal "
                + "of Binary Tree is ");
        tree.printSpecificLevelOrder(tree.root);
    }
}
  
// This code has been contributed by Mayank Jaiswal(mayank_24)

Python3

# Python program for special order traversal
  
# A binary tree ndoe
class Node:
      
    # Create queue and enqueue left
    # and right child of root
    s = []
    q = []
      
    # Variable to traverse the reversed array
    elements = 0
      
    # A constructor for making a new node
    def __init__(self, key):
        self.data = key
        self.left = None
        self.right = None
  
    # Given a perfect binary tree print 
    # its node in specific order
    def printSpecificLevelOrder(self, root):
        self.s.append(root)
          
        # Pop the element from the list
        prnt = self.s.pop(0)
        self.q.append(prnt.data)
        if prnt.right:
            self.s.append(root.right)
        if prnt.left:
            self.s.append(root.left)
              
        # Traversal loop
        while(len(self.s) > 0):
              
            # Pop two items from queue
            first = self.s.pop(0)
            self.q.append(first.data)
            second = self.s.pop(0)
            self.q.append(second.data)
              
            # Since it is perfect Binary tree,
            # one of the node is needed to be checked
            if first.left and second.right and first.right and second.left:
                  
                # If first and second have grandchildren,
                # enqueue them in reverse order
                self.s.append(first.left)
                self.s.append(second.right)
                self.s.append(first.right)
                self.s.append(second.left)
  
        # Give a perfect binary tree print 
        # its node in reverse order
        for elements in reversed(self.q):
            print(elements, end=" ")
  
  
# Driver Code
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)
  
root.left.left.left = Node(8)
root.left.left.right = Node(9)
root.left.right.left = Node(10)
root.left.right.right = Node(11)
root.right.left.left = Node(12)
root.right.left.right = Node(13)
root.right.right.left = Node(14)
root.right.right.right = Node(15)
  
root.left.left.left.left = Node(16)
root.left.left.left.right = Node(17)
root.left.left.right.left = Node(18)
root.left.left.right.right = Node(19)
root.left.right.left.left = Node(20)
root.left.right.left.right = Node(21)
root.left.right.right.left = Node(22)
root.left.right.right.right = Node(23)
root.right.left.left.left = Node(24)
root.right.left.left.right = Node(25)
root.right.left.right.left = Node(26)
root.right.left.right.right = Node(27)
root.right.right.left.left = Node(28)
root.right.right.left.right = Node(29)
root.right.right.right.left = Node(30)
root.right.right.right.right = Node(31)
'''
print("Specific Level Order traversal of "
                         "binary tree is")
root.printSpecificLevelOrder(root)
  
  
# This code is contributed by 'Vaibhav Kumar 12'

C#

// C# program for special order traversal 
using System;
using System.Collections.Generic;
  
/* A binary tree node has data, 
pointer to left child and a 
pointer to right child */
public class Node
{
    public int data;
    public Node left, right;
  
    public Node(int data)
    {
        this.data = data;
        left = right = null;
    }
}
  
class GFG
{
public Node root;
  
public virtual void printSpecificLevelOrderUtil(Node root, 
                                                Stack<Node> s)
{
    if (root == null)
    {
        return;
    }
  
    // Create a queue and enqueue left 
    // and right children of root 
    LinkedList<Node> q = new LinkedList<Node>();
  
    q.AddLast(root.left);
    q.AddLast(root.right);
  
    // We process two nodes at a time, so we 
    // need two variables to store two front 
    // items of queue 
    Node first = null, second = null;
  
    // traversal loop 
    while (q.Count > 0)
    {
        // Pop two items from queue 
        first = q.First.Value;
        q.RemoveFirst();
        second = q.First.Value;
        q.RemoveFirst();
  
        // Push first and second node's 
        // children in reverse order 
        s.Push(second.left);
        s.Push(first.right);
        s.Push(second.right);
        s.Push(first.left);
  
        // If first and second have grandchildren, 
        // enqueue them in specific order 
        if (first.left.left != null)
        {
            q.AddLast(first.right);
            q.AddLast(second.left);
            q.AddLast(first.left);
            q.AddLast(second.right);
        }
    }
}
  
/* Given a perfect binary tree, 
print its nodes in specific 
level order */
public virtual void printSpecificLevelOrder(Node root)
{
    // create a stack and push root 
    Stack<Node> s = new Stack<Node>();
  
    // Push level 1 and level 2 
    // nodes in stack 
    s.Push(root);
  
    // Since it is perfect Binary Tree, 
    // right is not checked 
    if (root.left != null)
    {
        s.Push(root.right);
        s.Push(root.left);
    }
  
    // Do anything more if there are 
    // nodes at next level in given
    // perfect Binary Tree 
    if (root.left.left != null)
    {
        printSpecificLevelOrderUtil(root, s);
    }
  
    // Finally pop all Nodes from 
    // stack and prints them. 
    while (s.Count > 0)
    {
        Console.Write(s.Peek().data + " ");
        s.Pop();
    }
}
  
// Driver Code
public static void Main(string[] args)
{
    GFG tree = new GFG();
    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.root.left.left.left.left = new Node(16); 
    tree.root.left.left.left.right = new Node(17); 
    tree.root.left.left.right.left = new Node(18); 
    tree.root.left.left.right.right = new Node(19); 
    tree.root.left.right.left.left = new Node(20); 
    tree.root.left.right.left.right = new Node(21); 
    tree.root.left.right.right.left = new Node(22); 
    tree.root.left.right.right.right = new Node(23); 
    tree.root.right.left.left.left = new Node(24); 
    tree.root.right.left.left.right = new Node(25); 
    tree.root.right.left.right.left = new Node(26); 
    tree.root.right.left.right.right = new Node(27); 
    tree.root.right.right.left.left = new Node(28); 
    tree.root.right.right.left.right = new Node(29); 
    tree.root.right.right.right.left = new Node(30); 
    tree.root.right.right.right.right = new Node(31); 
    */
    Console.WriteLine("Specific Level Order Traversal " +
                                   "of Binary Tree is ");
    tree.printSpecificLevelOrder(tree.root);
}
}
  
// This code is contributed by Shrikant13

Output : 

Specific Level Order traversal of binary tree is 
2 3 1

Approach 2: (Using vector)

  1. We will traverse each level top to down and we will push each level to stack from top to down
  2. so, that we can have finally down to up printed levels,
  3. we are having a level in a vector so we can print it in any defined way,

C++

/* C++ program for special order traversal */
#include<bits/stdc++.h>
using namespace std;
  
/* A binary tree node has data, pointer to left child
and a pointer to right child */
class Node
{
    public:
        int data;
        Node* left;
        Node* right;
          
        /* Helper function that allocates a new node with the
        given data and NULL left and right pointers. */
        Node(int value)
        {
            data = value;
            left = NULL;
            right = NULL;
        }
};
  
/* Given a perfect binary tree, print its nodes in
specific level order */
void specific_level_order_traversal(Node* root)
{
    //for level order traversal
    queue <Node*> q;
    // stack to print reverse
    stack < vector <int> > s; 
      
    q.push(root);
    int sz;
      
    while(!q.empty())
    {
        vector <int> v;    //vector to store the level
        sz = q.size();    //considering size of the level
          
        for(int i=0;i<sz;++i)
        {
            Node* temp = q.front();
            q.pop();
              
            //push data of the node of a particular level to vector
            v.push_back(temp->data); 
              
            if(temp->left!=NULL)
            q.push(temp->left);
      
            if(temp->right!=NULL)
                q.push(temp->right);
        }
          
        //push vector containg a level in stack
        s.push(v); 
    }
      
    //print the stack
    while(!s.empty())
    {
        // Finally pop all Nodes from stack and prints
        // them.
        vector <int> v = s.top();
        s.pop();
        for(int i=0,j=v.size()-1;i<j;++i)
            {
                cout<<v[i]<<" "<<v[j]<<" ";
                j--;
            }
    }
      
    //finally print root;
    cout<<root->data;
      
}
  
// Driver code
int main()
{
    Node *root = new Node(1);
  
    root->left = new Node(2);
    root->right = new Node(3);
  
/*    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->left = new Node(12);
    root->right->left->right = new Node(13);
    root->right->right->left = new Node(14);
    root->right->right->right = new Node(15);
  
    root->left->left->left->left = new Node(16);
    root->left->left->left->right = new Node(17);
    root->left->left->right->left = new Node(18);
    root->left->left->right->right = new Node(19);
    root->left->right->left->left = new Node(20);
    root->left->right->left->right = new Node(21);
    root->left->right->right->left = new Node(22);
    root->left->right->right->right = new Node(23);
    root->right->left->left->left = new Node(24);
    root->right->left->left->right = new Node(25);
    root->right->left->right->left = new Node(26);
    root->right->left->right->right = new Node(27);
    root->right->right->left->left = new Node(28);
    root->right->right->left->right = new Node(29);
    root->right->right->right->left = new Node(30);
    root->right->right->right->right = new Node(31);*/
    cout << "Specific Level Order traversal of binary "
        "tree is ";
    specific_level_order_traversal(root);
    return 0;
}
// This code is contributed by Rachit Yadav.


Output : 

Specific Level Order traversal of binary tree is 
2 3 1


This article is attributed to GeeksforGeeks.org

tags:

Tree tree-level-order Tree
Prev Next
More topics on Binary Tree Data Structure

leave a comment

code

0 Comments

load comments

Subscribe to Our Newsletter

Top Followed books

Binary Tree Data S... Inorder Tree Traversal without...
Binary Tree Data S... Construct Full Binary Tree usi...
Binary Tree Data S... Construct a complete binary tr...
Binary Tree Data S... Tree Traversals (Inorder, Preo...
Binary Tree Data S... Expression Tree
Binary Tree Data S... Evaluation of Expression Tree