{"id":1860,"date":"2024-03-06T21:00:00","date_gmt":"2024-03-06T21:00:00","guid":{"rendered":"https:\/\/favtutor.com\/articles\/?p=1860"},"modified":"2024-03-08T09:00:42","modified_gmt":"2024-03-08T09:00:42","slug":"binary-tree-right-side-view","status":"publish","type":"post","link":"https:\/\/favtutor.com\/articles\/binary-tree-right-side-view\/","title":{"rendered":"Print Right Side View of Binary Tree (with code)"},"content":{"rendered":"\n

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.<\/p>\n\n\n\n

Binary Tree Right Side View Problem<\/strong><\/h2>\n\n\n\n

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. <\/strong><\/p>\n\n\n\n

Let\u2019s try to understand this with an example:<\/p>\n\n\n

\n
\"Right<\/figure>\n<\/div>\n\n\n

Values you can see are highlighted in the tree from the right side.<\/p>\n\n\n\n

\"Right<\/figure>\n\n\n\n

Iterative Method<\/strong><\/h2>\n\n\n\n

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. <\/p>\n\n\n\n

Here is the process step-by-step:<\/p>\n\n\n\n

    \n
  1. Create a queue that stores the address of each node of the tree. <\/li>\n\n\n\n
  2. Push the root into the queue and a Null value.<\/li>\n\n\n\n
  3. Now iterate over the queue till it is not empty. Make a variable name sz which stores the current size of the queue.<\/li>\n\n\n\n
  4. Iterate a loop of size sz. <\/li>\n\n\n\n
  5. 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.<\/li>\n\n\n\n
  6. If the value is null simply pop this element and move to the next one by pushing a null value into the queue.<\/li>\n\n\n\n
  7. If not, then push its left and right values if exist.<\/li>\n\n\n\n
  8. Return the resultant array once all iterations are done.<\/li>\n<\/ol>\n\n\n\n

    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.<\/p>\n\n\n\n

    Recursive Method<\/strong><\/h2>\n\n\n\n

    We can print the right-side view of a binary tree using recursion. <\/strong>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. <\/p>\n\n\n\n

    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.<\/p>\n\n\n\n

    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<\/a> here.<\/p>\n\n\n\n

    Let\u2019s understand this with an example:<\/p>\n\n\n\n

    \"Input<\/figure>\n\n\n\n