Interview Course Based on Story Questions

# Description

You are given a binary tree `T`. Imagine you are standing to the right of it; you have to return the value of the nodes you can see from top to bottom.


You have to return the rightmost nodes on their respective levels in the form of an array.

Let’s discuss an example below:

class TreeNode {
public:
    int val;
    TreeNode *left;
    TreeNode *right;
    TreeNode() {
        this-> val = 0;
    }
    TreeNode(int x) {
        this->val = x;
        this->right = nullptr;
        this->left = nullptr;
    }
    TreeNode(int x, TreeNode *left, TreeNode *right) {
        this->val = x;
        this->left = left;
        this->right = right;
    }
    ~TreeNode(){
        delete this->left;
        delete this->right;
    }
};

#include "TreeNode.h"
std::vector<int> rightSideView(TreeNode* root){
    return {};
}

class TreeNode(object):
    def __init__(self, val=0, left=None, right=None):
        self.val = val
        self.left = left
        self.right = right

from TreeNode import *
def right_side_view(root):
  # write your code here
  pass

Python

public class TreeNode {
    public int val;
    public TreeNode left;
    public TreeNode right;
    public TreeNode() {}
    public TreeNode(int val) { this.val = val; }
    public TreeNode(int val, TreeNode left, TreeNode right) {
          this.val = val;
          this.left = left;
          this.right = right;
    }
}

class Solution {
    public static List<Integer> rightSideView(TreeNode root) {
        // write your code here 
        return new ArrayList<Integer>();
    }
}

Java

export class TreeNode{
    constructor(val=0, left=null, right=null){
        this.val = val
        this.left = left
        this.right = right
    }
}

import {TreeNode} from './TreeNode.js'

function rightSideView(root){
  // write your code here
  
  return []
}

# Solution
We can use a _depth-first search (DFS)_ to solve this problem. The intuition here is to traverse the tree _level by level_ recursively, starting from the `rightmost` node for each recursive call.

Let's review the implementation below:


#include "TreeNode.h"
void DFS(TreeNode* node, int level, std::vector<int>& rightside) {
    if (level == rightside.size()) 
        rightside.push_back(node->val);
    
    if (node->right != nullptr) 
        DFS(node->right, level + 1, rightside);  
    if (node->left != nullptr) 
        DFS(node->left, level + 1, rightside);
}    
    
std::vector<int> rightSideView(TreeNode* root) {
    if (root == nullptr) return {};
    
    std::vector<int> rightside;
    DFS(root, 0, rightside);
    
    return rightside;
}
int main(){
    // Driver Code
    TreeNode* root = new TreeNode(1);
    root->left = new TreeNode(2);
    root->right = new TreeNode(3);
    root->left->left = new TreeNode(4);
    root->left->right = new TreeNode(5);

    root->right->left = new TreeNode(6);
    root->right->right = new TreeNode(7);
    root->right->right->left = new TreeNode(8);
    auto res = rightSideView(root);
    print(res);
    return 0;
}

#include<iostream>
#include<vector>

void print(std::vector<int>& vec){
    std::cout << "[";
    for(int i = 0; i < vec.size(); i++){
        std::cout << std::to_string(vec[i]);
        if(i + 1< vec.size()){
            std::cout <<", ";
        }
    }
    std::cout << "]" << std::endl;
}

from TreeNode import *
def right_side_view(root):
  if root is None:
      return []
  rightside = []
  
  def DFS(node: TreeNode, level: int) -> None:
      if level == len(rightside):
          rightside.append(node.val)
      for child in [node.right, node.left]:
          if child:
              DFS(child, level + 1)
          
  DFS(root, 0)
  return rightside


# Driver Code
root = TreeNode(1)
root.left = TreeNode(2)
root.right = TreeNode(3)
root.left.left = TreeNode(4);
root.left.right = TreeNode(5);

root.right.left = TreeNode(6);
root.right.right = TreeNode(7);
root.right.right.left = TreeNode(8);
print(right_side_view(root))

class Solution {    
    public static void DFS(TreeNode node, int level, List<Integer> rightside) {
        if (level == rightside.size()) 
            rightside.add(node.val);
        
        if (node.right != null) 
            DFS(node.right, level + 1, rightside);  
        if (node.left != null) 
            DFS(node.left, level + 1, rightside);
    }    
    
    public static List<Integer> rightSideView(TreeNode root) {
        List<Integer> rightside = new ArrayList<Integer>();

        if (root == null) return rightside;
        DFS(root, 0, rightside);
        return rightside;
    }

    public static void main(String args[]){
        TreeNode root = new TreeNode(1);
        root.left = new TreeNode(2);
        root.right = new TreeNode(3);
        root.left.left = new TreeNode(4);
        root.left.right = new TreeNode(5);

        root.right.left = new TreeNode(6);
        root.right.right = new TreeNode(7);
        root.right.right.left = new TreeNode(8);
        System.out.println("" + rightSideView(root));
    }
}

import {TreeNode} from './TreeNode.js'
function rightSideView(root){
  if (root == null)
    return []
  var rightside = []
  
  function DFS(node, level){
    if (level == rightside.length)
      rightside.push(node.val)
    temp = [node.right, node.left]
    temp.forEach((child) => {
      if (child != null)
        DFS(child, level + 1)
    })
  }
          
  DFS(root, 0)
  return rightside
}


// Driver Code
var root = new TreeNode(1)
root.left = new TreeNode(2)
root.right = new TreeNode(3)
root.left.left = new TreeNode(4);
root.left.right = new TreeNode(5);

root.right.left = new TreeNode(6);
root.right.right = new TreeNode(7);
root.right.right.left = new TreeNode(8);
console.log(rightSideView(root))

# Complexity measures
| **Time Complexity** | **Space Complexity** |
| --- | --- |
| $O(N)$ | $O(H)$ |

## Time complexity
The time complexity will be $O(N)$, where `N` is the number of nodes because we have to visit all the nodes.
## Space complexity
The space complexity will be $O(D)$, where `H` is the _height_ of the tree. In the worst case, we can have `N` nodes in the recursion stack of a skewed tree. Therefore, the space complexity will be `O(N)` in the worst case.

Binary Tree Right Side View

Description