Problem Statement:
Given a binary tree, print the left and right view of the tree.
For example:
If you have a tree as below:
The left view will be a, b, d, h and right view will be a, c, g, j. As highlighted in image below.
So how do we solve this problem?
We can easily solve it by 2 steps
- Get the level order traversal
- The starting node for all the level order traversal will be the left view
- The ending node at each level will be the right view.
Step 1: The level order traversal for the above binary tree will be:
a,
b, c
d, e, f, g
h, i, j
For left view get the first node at each level:
a, b, d, h
For right view get the last node at each level
a, c, g, j
Hence the solution.
How to do it programatically?
To print the left view of a binary tree, look at the below code snippet:
int max_level = 0; void print_left_view(Node *node, int level) { if(node == NULL) { return; } if(level >= max_level) { cout<<node->data << " "; max_level++; } print_left_view(node->left, level + 1); print_left_view(node->right, level + 1); }
Here we have taken a “max_level” variable and set it to 0.
We print the node data, whenever the level is greater than equal to max_level. Thus printing the left view.
For example:
If we have only 1 node as below:
So, initially, level will be 0 and max_level will also be 0. So we print the root node.
If we have binary tree as below:
So, initially, level will be 0 and max_level will also be 0. So we print the root node and increment the max_level. Now max_level will be 1.
Then we go to the left node, we recursively call “print_left_view” with the left node and increasing the level. Now level will be 1.
Now again the level and max_level matches, we print the left node.
When it goes to right node, we recursively call “print_left_view” with right node and increase the level. Now level will be 2.
But the max_level is 1, condition will not satisfy, hence it will not print the right node.
We do the same operation for right view. But here we will call the right node first, instead of calling the left node.
Solution in C++
#include <iostream> #include <queue> #include <stack> using namespace std; // structure to hold binary tree node struct Node { int data; Node *left, *right; Node(int data) { this->data = data; this->left = this->right = nullptr; } }; int max_level_left = 0; void print_left_view(Node *node, int level) { if(node == NULL) { return; } if(level >= max_level_left) { cout<<node->data << " "; max_level_left++; } print_left_view(node->left, level + 1); print_left_view(node->right, level + 1); } int max_level_right = 0; void print_right_view(Node *node, int level) { if(node == NULL) { return; } if(level >= max_level_right) { cout<<node->data << " "; max_level_right++; } print_right_view(node->right, level + 1); print_right_view(node->left, level + 1); } int main() { Node* root = nullptr; /* Binary tree: 16 / \ / \ 10 25 / \ / \ / \ / \ 7 15 18 30 */ root = new Node(16); root->left = new Node(10); root->right = new Node(25); root->left->left = new Node(7); root->left->right = new Node(15); root->right->left = new Node(18); root->right->right = new Node(30); cout<<"Left view = " ; print_left_view(root, 0); cout<<endl; cout<<"Right view = " ; print_right_view(root, 0); cout<<endl; return 0; }
Output:
Left view = 16 10 7 Right view = 16 25 30