menu

### Binary Tree Right Side View

**Problem Statement:** Given the `root`

of a binary tree, imagine yourself standing on the **right side** of it, return *the values of the nodes you can see ordered from top to bottom*.

##
Examples

**Example 1:**

Input:root = [1,2,3,null,5,null,4]Output:[1,3,4]

**Example 2:**

Input:root = [1,null,3]Output:[1,3]

**Example 3:**

Input:root = []Output:[]

##
Constraints

- The number of nodes in the tree is in the range
`[0, 100]`

. `-100 <= Node.val <= 100`

### Solution

##
Optimised Approach

##### Algorithm

Using Reverse Preorder Traversal

##### Intuition

Imagine walking through a forest of connected branches (that’s our tree!). To see only the trees on the right side, we follow a path that always leans to the right. We start at the tree’s top and move to the right, peeking at each level to see what’s there.

We use a trick called ‘recursion’ to move through the tree. This means we keep doing the same thing but on smaller parts of the tree until we’re done.

The ‘level’ here helps us keep track of how deep we are in the tree. Whenever we find a new right-side tree at a certain level, we jot it down in our list of findings.

By doing this, step by step, we create a list that shows only the trees on the right side. It’s like taking a special path through the forest that lets us see only the trees on our right as we move along.

##### Short Video Explanation

For a better understanding of the algorithm, please watch the video by clicking on the button below.

##### Code

` ````
```/**
* Definition for a binary tree node.
* struct TreeNode {
* int val;
* TreeNode *left;
* TreeNode *right;
* TreeNode() : val(0), left(nullptr), right(nullptr) {}
* TreeNode(int x) : val(x), left(nullptr), right(nullptr) {}
* TreeNode(int x, TreeNode *left, TreeNode *right) : val(x), left(left), right(right) {}
* };
*/
class Solution {
public:
int levels(TreeNode* root)
{
if(root==NULL) return 0;
return 1 + max(levels(root->left),levels(root->right));
}
void returnRightSideView(TreeNode* root,vector& ans,int curr)
{
if(root==NULL) return;
ans[curr] = root->val;
returnRightSideView(root->left,ans,curr+1);
returnRightSideView(root->right,ans,curr+1);
}
vector rightSideView(TreeNode* root) {
int level = levels(root);
vector ans(level);
returnRightSideView(root,ans,0);
return ans;
}
};

` ````
```# Definition for a binary tree node.
# class TreeNode:
# def __init__(self, val=0, left=None, right=None):
# self.val = val
# self.left = left
# self.right = right
class Solution:
def rightSideView(self, root: Optional[TreeNode]) -> List[int]:
level=0
result=[]
def rootRightLeft(node,level):
if not node:
return
if level==len(result):
result.append(node.val)
rootRightLeft(node.right,level+1)
rootRightLeft(node.left,level+1)
rootRightLeft(root,0)
return result

` ````
```/**
* Definition for a binary tree node.
* public class TreeNode {
* int val;
* TreeNode left;
* TreeNode right;
* TreeNode() {}
* TreeNode(int val) { this.val = val; }
* TreeNode(int val, TreeNode left, TreeNode right) {
* this.val = val;
* this.left = left;
* this.right = right;
* }
* }
*/
class Solution {
public List rightSideView(TreeNode root) {
List res = new ArrayList<>();
dfs(root, res, 1);
return res;
}
private void dfs(TreeNode node, List res, int depth) {
if (node == null) {
return;
}
if (depth > res.size()) {
res.add(node.val);
}
dfs(node.right, res, depth + 1);
dfs(node.left, res, depth + 1);
}
}

##### Explanation

**Initialization:**`level`

is set to 0, indicating the depth or level of the tree nodes.`result`

starts as an empty list where we’ll store the values of nodes seen from the right side.

**Traversal Function:**`rootRightLeft`

is a function that takes in a`node`

and its`level`

.- If the
`node`

is empty (or null), the function stops and returns. - If the current
`level`

matches the length of the`result`

list, it implies that this is the rightmost node at this depth, so its value is appended to`result`

. - The function then recursively calls itself first on the right child of the current node and then on the left child, incrementing the level by 1 each time.

**Execution:**- The
`rootRightLeft`

function is initially called with the tree’s root node and a starting level of 0. - This triggers the recursive traversal, moving through the tree to identify and collect the values of nodes seen from the right side.

- The
**Return:**- Finally, the function returns the
`result`

list containing the values of nodes seen from the right side of the tree.

- Finally, the function returns the

##### Explanation

- Starting from the root, the function moves to the right child, checking each level for the rightmost node.
- It explores the right subtree, appending the rightmost nodes’ values to the
`result`

list. - Then, it moves to the left subtree, but it doesn’t append any values since those wouldn’t be on the right side.
- The process continues recursively until all nodes have been traversed, and the
`result`

list contains the values seen from the right side of the tree.

##### Time and Space Complexity

__Time Complexity:__ O(N)

__Space Complexity:__ O(H) where H is height of the tree

WhatsApp

Facebook

Twitter

LinkedIn

Email