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.
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.
- Instead of processing ONE node at a time, we will process TWO nodes at a time.
- 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.
- 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.
- 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)
- We will traverse each level top to down and we will push each level to stack from top to down
- so, that we can have finally down to up printed levels,
- 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
leave a comment
0 Comments