Perfect Binary Tree Specific Level Order Traversal - GeeksforGeeks
Given a Perfect Binary Tree like below:
The standard level order traversal idea will slightly change here. Instead of processing ONE node at a time, we will process TWO nodes at a time. And while pushing children into queue, the enqueue order will be: 1st node’s left child, 2nd node’s right child, 1st node’s right child and 2nd node’s left child.
We can do standard level order traversal here too but instead of printing nodes directly, we have to store nodes in current level in a temporary array or list 1st and then take nodes from alternate ends (left and right) and print nodes. Keep repeating this for all levels.
This approach takes more memory than standard traversal.
Read full article from Perfect Binary Tree Specific Level Order Traversal - GeeksforGeeks
Given a Perfect Binary Tree like below:
Print the level order of nodes in following specific manner:
1 2 3 4 7 5 6 8 15 9 14 10 13 11 12 16 31 17 30 18 29 19 28 20 27 21 26 22 25 23 24
i.e. print nodes in level order but nodes should be from left and right side alternatively. Here 1st and 2nd levels are trivial.
While 3rd level: 4(left), 7(right), 5(left), 6(right) are printed.
While 4th level: 8(left), 15(right), 9(left), 14(right), .. are printed.
While 5th level: 16(left), 31(right), 17(left), 30(right), .. are printed.
Approach 2:While 3rd level: 4(left), 7(right), 5(left), 6(right) are printed.
While 4th level: 8(left), 15(right), 9(left), 14(right), .. are printed.
While 5th level: 16(left), 31(right), 17(left), 30(right), .. are printed.
The standard level order traversal idea will slightly change here. Instead of processing ONE node at a time, we will process TWO nodes at a time. And while pushing children into queue, the enqueue order will be: 1st node’s left child, 2nd node’s right child, 1st node’s right child and 2nd node’s left child.
void
printSpecificLevelOrder(Node *root)
{
if
(root == NULL)
return
;
// Let us print root and next level first
cout << root->data;
// / Since it is perfect Binary Tree, right is not checked
if
(root->left != NULL)
cout <<
" "
<< root->left->data <<
" "
<< root->right->data;
// Do anything more if there are nodes at next level in
// given perfect Binary Tree
if
(root->left->left == 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();
// Print children of first and second in reverse order
cout <<
" "
<< first->left->data <<
" "
<< second->right->data;
cout <<
" "
<< first->right->data <<
" "
<< second->left->data;
// If first and second have grandchildren, enqueue them
// in reverse order
if
(first->left->left != NULL)
{
q.push(first->left);
q.push(second->right);
q.push(first->right);
q.push(second->left);
}
}
}
Followup Questions:
- The above code prints specific level order from TOP to BOTTOM. How will you do specific level order traversal from BOTTOM to TOP (Amazon Interview | Set 120 – Round 1 Last Problem)
- What if tree is not perfect, but complete.
- What if tree is neither perfect, nor complete. It can be any general binary tree.
We can do standard level order traversal here too but instead of printing nodes directly, we have to store nodes in current level in a temporary array or list 1st and then take nodes from alternate ends (left and right) and print nodes. Keep repeating this for all levels.
This approach takes more memory than standard traversal.
Read full article from Perfect Binary Tree Specific Level Order Traversal - GeeksforGeeks