Binary Tree Right Side View LeetCode Solution

Problem Statement

Binary Tree Right Side View LeetCode Solution – Given the root of a binary tree, imagine yourself standing on the right side of it, and return the values of the nodes you can see ordered from top to bottom.

Example

Test Case 1:

Input:

root = [1, 2, 3, null, 5, null, 4]

Output:

[1, 3, 4]

Approach:

A problem dealing with tree traversal typically means a breadth first search or a depth first search approach. Since we’re tasked with isolating a value from each level, this would naturally bring to mind the BFS approach… but let’s keep DFS on the back burner; we’ll come back to it.

A BFS approach usually entails the use of a queue (q) where we push each node’s children onto q while we move along a level of the tree from one side to the other. This ensures that when each level is completed, we have the next level ready to go in q. In order to separate each level, since we’re continuously adding to q, we can just take the length of q at the beginning of each level to figure out when the next one begins.

In this case, we can run our BFS from right to left and simply push the first value of each level in our answer array (ans) before returning the array upon complete traversal of the tree.

But what about the DFS approach? DFS solutions often allow us to find a concise, recursive solution, and while they’re not always the first thought when it comes to tree traversal problems where the level is important, in this case we don’t need the level as a whole, we just need one end of each level.

This means that we can define a recursive function (dfs) to run through the nodes from left to right and simply overwrite the value for each level (ans[lvl]) as we get to each node, since the last value from left to right on each level will be the one we want to keep.

stepwise

1. declare a vector storing int values
2. declare a queue storing node type value(TreeNode*)
3. push root into queue
4. work until queue is not empty
5. iterate until last element present in queue and push last element of current queue size
6. check for left and right node if null or not
7. Repeat steps from 4 to 6
8. return the vector.

Code for Binary Tree Right Side View

C++ Program

/**
 * 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:
    vector<int> rightSideView(TreeNode* root) {
        if(!root) {
            return {};
        }
        vector<int> v; //store values of nodes in the rightmost
        queue<TreeNode*> Q; //store node type values in queue 
        Q.push(root); //push root
        while(!Q.empty()) { //repeat steps until queue is not empty
            
            int size = Q.size();  // current size of queue
            for(int i = 0; i < size; i++) {
              TreeNode* t = Q.front(); //declare a temp node and put front node of queue
                Q.pop(); 
                if(i==size-1) {   //if node is rightmost 
                    v.push_back(t->val); //push the value of rightmost node into vector
                }
                if(t->left) {   //if temp->left != NULL then push into queue
                    Q.push(t->left);
                }
                if(t->right) { //if temp->right != NULL then push into queue
                    Q.push(t->right);
                }
            }  
        }
        return v; //finally we have all values
    }
};

Python Program

from collections import deque
class Solution(object):
    def rightSideView(self, root):
        """
        :type root: TreeNode
        :rtype: List[int]
        """
        right_v, q = [], deque()
        if root:
            q.append(root)
        while len(q):
            right_v.append(q[-1].val)
            for i in range(len(q)):
                top = q.popleft()
                if top.left:
                    q.append(top.left)
                if top.right:
                    q.append(top.right)
        return right_v

Complexity Analysis for Binary Tree Right Side View LeetCode Solution

Time Complexity: O(n)

Space Complexity: O(n) due to queue