Learning Journal

3/2/2024

Binary Right Side View - DFS approach

Tags: algorithms leetcode binary_tree depth_first_search

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

THE PROBLEM

The depth-first search approach to this problem is very interesting. Let me try to understand it.

The idea comes when you recognize that if you number the level of the tree from 0 to h with h is the height of the tree, the level number is also the index of its rightmost value in the rightside array. For example, the index of the rightmost's value at level 0 should be at index 0 of the rightside array, which is 1 whereas the index of the rightmost's value at level 1 should be at index 1 of the rightside array, which is 3.

So, we go to the right most node of the tree at each level and add its value to the right position of the result array. If the right most level is not there, we go to the one right at the left of it.

Revised by ChatGPT

This problem requires us to find the right side view of a binary tree. The right side view is defined as the set of nodes visible when the tree is viewed from the right side.

To solve this problem, I used a depth-first search (DFS) approach. The key idea is to traverse the tree in a way that ensures we visit the rightmost node at each level first. Here's how the algorithm works:

Initialization: Create an empty list rightside to store the right side view of the tree.

Helper Function: Define a recursive helper function that takes a node and its level as arguments. The function performs the following steps:
    If the level is equal to the size of the rightside list, it means we've encountered the first node at this level (which is also the rightmost node), so we add its value to the list.
    Recursively call the helper function on the right child, then the left child, to ensure we visit the rightmost nodes first.

Main Function: In the rightSideView method, we check if the root is null. If not, we call the helper function with the root node and level 0.

By following this approach, we ensure that we visit the rightmost node at each level first and add it to the rightside list, giving us the right side view of the binary tree.