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.

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: []
  1. The number of nodes in the tree is in the range [0, 100].
  2. -100 <= Node.val <= 100

Solution

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<int>& ans,int curr)
    {
        if(root==NULL) return;
        ans[curr] = root->val;
        returnRightSideView(root->left,ans,curr+1);
        returnRightSideView(root->right,ans,curr+1);

    }
    vector<int> rightSideView(TreeNode* root) {
        int level = levels(root);
        vector<int> 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<Integer> rightSideView(TreeNode root) {
        List<Integer> res = new ArrayList<>();
        dfs(root, res, 1);
        return res;
    }

    private void dfs(TreeNode node, List<Integer> 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
  1. Initialization:

    1. level is set to 0, indicating the depth or level of the tree nodes.
    2. result starts as an empty list where we’ll store the values of nodes seen from the right side.
  2. Traversal Function:

    1. rootRightLeft is a function that takes in a node and its level.
    2. If the node is empty (or null), the function stops and returns.
    3. 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.
    4. 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.
  3. Execution:

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

    1. Finally, the function returns the result list containing the values of nodes seen from the right side of the tree.
  1.  
Explanation
  1. Starting from the root, the function moves to the right child, checking each level for the rightmost node.
  2. It explores the right subtree, appending the rightmost nodes’ values to the result list.
  3. Then, it moves to the left subtree, but it doesn’t append any values since those wouldn’t be on the right side.
  4. 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

Leave a Reply

Your email address will not be published. Required fields are marked *

Welcome to our diverse learning options!

Select the learning format that suits your preferences and schedule.