Solution For 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: []

Approach:

We can solve this problem using BFS (Breadth First Search) technique. The idea is to traverse the tree level by level and always keep the last node value of each level. So, the rightmost nodes will be visible from the right side of the binary tree.

Algorithm:
1. Create a list named result to store the right-side view of the binary tree.
2. Check if the given root is null or not.
3. If the root is null, then return the empty list result.
4. Initialize the queue with the root node.
5. Loop through the queue till it is empty:
a. initialize the size equal to the length of the queue.
b. Traverse each node level-wise from left to right.
c. Check if the node is the last node for that level, then appent that node’s value to the result list.
d. If the left child of the node exists, then append it to the queue.
e. If the right child of the node exists, then append it to the queue.
6. Finally return the result list, which contains the right-side view of the binary tree.

Code:

Here is the implementation of the algorithm in Python:

def rightSideView(root):
result = [] if root is None:
return result

queue = [root]
while queue:
    size = len(queue)
    for i in range(size):
        node = queue.pop(0)
        if i == size-1:
            result.append(node.val)
        if node.left:
            queue.append(node.left)
        if node.right:
            queue.append(node.right)

return result

Time Complexity:

The time complexity of the above algorithm is O(n), where n is the number of nodes in the binary tree. We traverse each node only once.

Space Complexity:

The space complexity of the above algorithm is O(n), where n is number of nodes in the binary tree. In the worst case, the queue can have all the nodes of the last level. So, the space complexity will be O(n).

This is the detailed solution of the Binary Tree Right Side View problem on Leetcode.

Step by Step Implementation For Binary Tree Right Side View

/**
 * 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) {
        // result list
        List result = new ArrayList<>();
        
        // base case
        if (root == null) {
            return result;
        }
        
        // level order traversal using a queue
        Queue queue = new LinkedList<>();
        queue.add(root);
        
        while (!queue.isEmpty()) {
            int size = queue.size();
            
            // iterate through all nodes of current level
            for (int i = 0; i < size; i++) {
                TreeNode curr = queue.remove();
                
                // add last node of current level to result
                if (i == size - 1) {
                    result.add(curr.val);
                }
                
                // add left and right child to queue
                if (curr.left != null) {
                    queue.add(curr.left);
                }
                if (curr.right != null) {
                    queue.add(curr.right);
                }
            }
        }
        
        return result;
    }
}

This is my solution for the leetcode problem binary-tree-right-side-view. Output should only consist of exact code with comments and nothing else.

# 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: TreeNode) -> List[int]:
        # Base case
        if not root:
            return []
        
        # Initialize a list to store the right side view
        right_side_view = []
        
        # Do a breadth first search
        queue = [root]
        while queue:
            # Get the size of the current level
            size = len(queue)
            
            # Iterate over all the nodes in the current level
            for i in range(size):
                # Get the node at the front of the queue
                node = queue.pop(0)
                
                # If this is the last node of the current level, add it to the right side view
                if i == size - 1:
                    right_side_view.append(node.val)
                
                # Add the left and right child nodes of the current node to the queue
                if node.left:
                    queue.append(node.left)
                if node.right:
                    queue.append(node.right)
        
        return right_side_view

/**
 * Definition for a binary tree node.
 * function TreeNode(val) {
 *     this.val = val;
 *     this.left = this.right = null;
 * }
 */
/**
 * @param {TreeNode} root
 * @return {number[]}
 */
var rightSideView = function(root) {
    // base case:
    if (!root) {
        return [];
    }
    
    // initialize our results array
    const results = [];
    
    // create a queue to help us do a breadth first traversal
    const queue = [root];
    
    // as long as there are nodes in the queue
    while (queue.length) {
        // get the number of nodes at the current level
        const levelSize = queue.length;
        
        // iterate over the nodes at the current level
        for (let i = 0; i < levelSize; i++) {
            // get the current node
            const currentNode = queue.shift();
            
            // if this is the last node in the level, add it to the results
            if (i === levelSize - 1) {
                results.push(currentNode.val);
            }
            
            // if the current node has a left child, add it to the queue
            if (currentNode.left) {
                queue.push(currentNode.left);
            }
            
            // if the current node has a right child, add it to the queue
            if (currentNode.right) {
                queue.push(currentNode.right);
            }
        }
    }
    
    // return the results
    return results;
};

/**
 * 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 rightSideView(TreeNode* root) {
        // Result vector
        vector result;
        
        // Base case
        if(root == nullptr) {
            return result;
        }
        
        // Queue for BFS
        queue q;
        q.push(root);
        
        while(!q.empty()) {
            // Get the size of the current level
            int size = q.size();
            
            // Iterate over all the nodes of the current level
            for(int i = 0; i < size; i++) {
                TreeNode* curr = q.front();
                q.pop();
                
                // Add the last node of the current level to the result
                if(i == size - 1) {
                    result.push_back(curr->val);
                }
                
                // Add the child nodes of the current node to the queue
                if(curr->left) {
                    q.push(curr->left);
                }
                if(curr->right) {
                    q.push(curr->right);
                }
            }
        }
        
        return result;
    }
};

public IList RightSideView(TreeNode root) {
    // create a list to store the right-most values
    List rightMostValues = new List();
    
    // create a queue to store the nodes at each level
    Queue nodes = new Queue();
    
    // add the root node to the queue
    nodes.Enqueue(root);
    
    // while there are still nodes in the queue
    while (nodes.Count > 0)
    {
        // create a list to store the nodes at the current level
        List currentLevel = new List();
        
        // loop through all of the nodes in the queue
        while (nodes.Count > 0)
        {
            // remove the first node from the queue and add it to the current level list
            TreeNode node = nodes.Dequeue();
            currentLevel.Add(node);
        }
        
        // add the right-most value of the current level to the rightMostValues list
        rightMostValues.Add(currentLevel[currentLevel.Count - 1].val);
        
        // loop through all of the nodes in the current level list
        for (int i = 0; i < currentLevel.Count; i++)
        {
            // if the left child exists, add it to the queue
            if (currentLevel[i].left != null)
            {
                nodes.Enqueue(currentLevel[i].left);
            }
            
            // if the right child exists, add it to the queue
            if (currentLevel[i].right != null)
            {
                nodes.Enqueue(currentLevel[i].right);
            }
        }
    }
    
    // return the list of right-most values
    return rightMostValues;
}