Given a binary tree, how do we print the right view of it?
For example, consider the simple binary tree below
For example, consider the simple binary tree below
1
/
2 3
The right view of this is 1, 3. Similarly consider one more example
1
/
2 5
/
3 4
Right view for this tree contains 1, 5, 4.
This is similar to my last post which asks for the left view of the binary tree. We just need to make the following changes to the algorithms discussed in the earlier post.
In case of iterative solution, we need to add the right child first to the queue before adding the left child.
In the recursive approach, we need to first recurse on the right child. Below is the modified code.
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> | |
| 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; | |
| } | |
| //Use level order traversing to find out the first node in each level | |
| //nodes at a particular level in the queue are separated by NULL node | |
| void printRightView(TreeNode *root) | |
| { | |
| if( root == NULL ) | |
| return; | |
| queue<TreeNode*> nodeQ; | |
| nodeQ.push(root); | |
| nodeQ.push(NULL); | |
| cout << root->val << " "; | |
| while( !nodeQ.empty() ) | |
| { | |
| TreeNode *temp = nodeQ.front(); | |
| nodeQ.pop(); | |
| if( temp == NULL ) | |
| { | |
| if( !nodeQ.empty() ) | |
| { | |
| temp = nodeQ.front(); | |
| cout << temp->val << " "; | |
| nodeQ.pop(); | |
| nodeQ.push(NULL); | |
| } | |
| } | |
| if( temp != NULL ) | |
| { | |
| if( temp->right != NULL ) | |
| nodeQ.push(temp->right); | |
| if( temp->left != NULL ) | |
| nodeQ.push(temp->left); | |
| } | |
| } | |
| cout << endl; | |
| } | |
| void printRightViewRecursive(TreeNode *root, int &maxLevel, int currentLevel) | |
| { | |
| if( root == NULL ) | |
| return; | |
| if( maxLevel < currentLevel ) | |
| { | |
| cout << root->val << " "; | |
| maxLevel = currentLevel; | |
| } | |
| printRightViewRecursive( root->right, maxLevel, currentLevel+1 ); | |
| printRightViewRecursive( root->left, maxLevel, currentLevel+1 ); | |
| } | |
| void rightViewRecursive(TreeNode *root) | |
| { | |
| int maxLevel = -1; | |
| printRightViewRecursive(root, maxLevel, 0); | |
| } | |
| void Test1() | |
| { | |
| TreeNode *root = NULL; | |
| root = insert(root, 2); | |
| root = insert(root, 1); | |
| root = insert(root, 4); | |
| root = insert(root, 3); | |
| root = insert(root, 5); | |
| printRightView(root); | |
| rightViewRecursive(root); | |
| cout << endl; | |
| } | |
| void Test2() | |
| { | |
| TreeNode *root = NULL; | |
| root = insert(root, 4); | |
| root = insert(root, 2); | |
| root = insert(root, 5); | |
| root = insert(root, 1); | |
| root = insert(root, 3); | |
| root = insert(root, 6); | |
| printRightView(root); | |
| rightViewRecursive(root); | |
| cout << endl; | |
| } | |
| int main() | |
| { | |
| Test1(); | |
| Test2(); | |
| return 0; | |
| } |
by