Java: Binary Tree Right Side View

Thought Process

To get the right side view of a binary tree, we can use a modified DFS approach. We traverse the tree in a right-to-left manner, ensuring that the first node encountered at each level is the rightmost node. We maintain a list to store the rightmost nodes, and we only add a node to the list if its level matches the current size of the list. This ensures that we capture the rightmost node at each level efficiently. 

/**
 * 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 void rightView(TreeNode root, List<Integer> ans, int level){

        if(root == null)
            return ;

        // I need one node (right mode one) from each level.
        // So, whenever level == ans.size() i will adding that nod's value in my list.
        if(ans.size()==level)
            ans.add(root.val);

        rightView(root.right,ans,level+1);
        rightView(root.left,ans,level+1);
    }
    public List<Integer> rightSideView(TreeNode root) {
        
        List<Integer> ans = new ArrayList<>();
        rightView(root,ans,0);

        return ans;
    }
}

Code Complexity

Time Complexity: O(n)

The algorithm visits each node exactly once, where 'n' is the number of nodes in the tree.

Space Complexity: O(h)

The space used by the recursion stack depends on the height of the tree (h). In the worst case, the space complexity is O(n).

Code copied!