Given a binary tree, how do we print the nodes in level order starting from the bottom.
For example for the following tree, the output should be 2 3 1
1
/
2 3
An obvious solution is to first find the maximum levels of the tree. we can print the nodes from maximum level to minimum level. This is not so efficient, because to print each level we need to traverse all the nodes.
Another solution is that we can modify the level order traversal. We need an additional stack to store the nodes. Instead of printing the values of the nodes as soon as they are deleted from the queue, we can add them to stack. Later, we can pop the elements from the stack and print them. This will print the elements in reverse level order.
Here is the C++ code for the second approach.
This file contains bidirectional Unicode text that may be interpreted or compiled differently than what appears below. To review, open the file in an editor that reveals hidden Unicode characters.
Learn more about bidirectional Unicode characters
| #include <iostream> | |
| #include <queue> | |
| #include <stack> | |
| using namespace std; | |
| //Binary tree node type | |
| struct TreeNode | |
| { | |
| int val; | |
| TreeNode *left, *right; | |
| TreeNode(int v):val(v),left(NULL), right(NULL) | |
| { | |
| } | |
| }; | |
| //Binary search tree insert procedure for creating binary tree to test | |
| TreeNode* insert(TreeNode * root, int data) | |
| { | |
| if( root == NULL ) | |
| { | |
| root = new TreeNode(data); | |
| return root; | |
| } | |
| if( data < root->val ) | |
| root->left = insert( root->left, data ); | |
| else | |
| root->right = insert( root->right, data ); | |
| return root; | |
| } | |
| void print_reverse_level_order(TreeNode *root) | |
| { | |
| if( root == NULL ) | |
| return; | |
| queue<TreeNode *> q; | |
| q.push(root); | |
| stack<TreeNode *> stk; | |
| while( !q.empty() ) | |
| { | |
| TreeNode *ptr = q.front(); | |
| q.pop(); | |
| stk.push(ptr); | |
| if( ptr->right != NULL ) | |
| q.push(ptr->right); | |
| if( ptr->left != NULL ) | |
| q.push(ptr->left); | |
| } | |
| while( !stk.empty() ) | |
| { | |
| TreeNode *temp = stk.top(); | |
| stk.pop(); | |
| cout << temp->val << " "; | |
| } | |
| cout << endl; | |
| } | |
| void Test() | |
| { | |
| int arr[] = {1,2,3,4,5,6,7}; | |
| TreeNode *root = create_balanced_tree(arr, 0, 6); | |
| print_reverse_level_order(root); | |
| } | |
| int main() | |
| { | |
| Test(); | |
| return 0; | |
| } |
by