A tree is a commonly used data structure that helps us to store and efficiently retrieve data. There are many technical questions asked in interviews. In this article, we will discuss one such problem where we have to print the Right Side View of a Binary Tree and implement the programs in different languages.
Binary Tree Right Side View Problem
In the Binary Tree Right Side View problem, we are given a binary tree and we have to return the right view of the binary tree i.e., if we stand on the right side of the tree we have to return the nodes we can see.
Let’s try to understand this with an example:
Values you can see are highlighted in the tree from the right side.
Iterative Method
In the iterative method, we will iterate through each level and then push the rightmost element into our resultant array. This can be accomplished by utilizing a queue data structure. We choose a queue because we will be inserting elements at the back and removing the topmost element.
Here is the process step-by-step:
- Create a queue that stores the address of each node of the tree.
- Push the root into the queue and a Null value.
- Now iterate over the queue till it is not empty. Make a variable name sz which stores the current size of the queue.
- Iterate a loop of size sz.
- Check if the value of the next element in the queue is Null, then push the current value into the resultant array as this would be the rightmost element at any level.
- If the value is null simply pop this element and move to the next one by pushing a null value into the queue.
- If not, then push its left and right values if exist.
- Return the resultant array once all iterations are done.
The time complexity for the above method is O(n) as we are iterating over the tree. Here n is the total number of nodes in the tree. Space complexity is O(n) as we are storing all values in a level in the queue.
Recursive Method
We can print the right-side view of a binary tree using recursion. We will first check if the current level of the node is the same as our size, then push this node value into the vector.
Now, we recursively call the right node of the current node by increasing the level and then the left node of the current node. We repeat the same process until we find the final bottom node on the right side.
This works because we first check all the right nodes and then the left ones, and if the level is the same as our size, then only we push the value into our array. You can check more differences between iteration and recursion here.
Let’s understand this with an example:
- At first, we have root as a first element in level 0 so we will push this into our array
- Next, we will move to node 3 as this is of level 1 and our array size is also 1, so we will push this into our array.
- Next, we will move to node 2, this is of level 1 and our array size is 2 so we will not push this into the array.
- Next, we will be at node 4, which is of level 2 and the size of the array is also 2, so we will push this into the array.
- Finally, we have Node 5. It is at level 3, and the size of the array is also 3. Therefore, we will push this value into the array.
- Now all nodes are done, return this array.
Let’s now move to code it.
C++ Code
Below is the C++ program to print the right view of the binary tree:
#include<bits/stdc++.h>
using namespace std;
class node{
public:
int value;
node* left;
node* right;
node(int a){
value = a;
left = NULL;
right = NULL;
}
};
void right_view(node* root, int level, vector<int>& arr){
if(root== NULL) return;
int n = arr.size();
if(n==level) arr.push_back(root->value);
//calling right side first.
right_view(root->right, level + 1, arr);
//calling left side.
right_view(root->left, level + 1,arr);
return;
}
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->left->right->left = new node(6);
//an array.
vector<int>ans;
// calling function right_view.
right_view(root,0,ans);
// printing values in the array.
for(int i=0;i<ans.size();i++){
cout<<ans[i]<<" ";
}
return 0;
}Java Code
We can implement the code in Java also:
import java.util.ArrayList;
class Node {
int value;
Node left;
Node right;
Node(int a) {
value = a;
left = null;
right = null;
}
}
public class Main {
static void rightView(Node root, int level, ArrayList<Integer> arr) {
if (root == null)
return;
int n = arr.size();
if (n == level)
arr.add(root.value);
// calling right side first.
rightView(root.right, level + 1, arr);
// calling left side.
rightView(root.left, level + 1, arr);
}
public static void main(String[] args) {
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.left.right.left = new Node(6);
// ans array.
ArrayList<Integer> ans = new ArrayList<>();
// calling function rightView.
rightView(root, 0, ans);
// printing values in the array.
for (int i = 0; i < ans.size(); i++) {
System.out.print(ans.get(i) + " ");
}
}
}Python Code
Here is the Python Solution for Binary Tree Right Side View problem:
class Node:
def __init__(self, a):
self.value = a
self.left = None
self.right = None
def right_view(root, level, arr):
if root is None:
return
n = len(arr)
if n == level:
arr.append(root.value)
# calling right side first.
right_view(root.right, level + 1, arr)
# calling left side.
right_view(root.left, level + 1, arr)
if __name__ == "__main__":
root = Node(1)
root.left = Node(2)
root.right = Node(3)
root.left.left = Node(4)
root.left.right = Node(5)
root.left.right.left = Node(6)
# ans array.
ans = []
# calling function right_view.
right_view(root, 0, ans)
# printing values in the array.
for val in ans:
print(val, end=" ")Output:
1 3 5 6The time complexity to print the right side view of a binary tree using recursion is O(n) where n is the total number of nodes. The space complexity will also be O(n) since we are recursively traversing each node.
Conclusion
In this article, we explore how we can print the right side view of a binary tree using iteration and recursion. This problem can also be found in leetcode. Recursion decreases both time and space complexity to some extent.
