binaryTreeRightSideView.java

// Given 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.

// Input: [1,2,3,null,5,null,4]
// Output: [1, 3, 4]
// Explanation:

//    1            <---
//  /   \
// 2     3         <---
//  \     \
//   5     4       <---


//Need to run BFS because it says top bottom,

//TC: O(N) to go through every node in bfs
//SC: O(N) to populate result array 

/**
 * Definition for a binary tree node.
 * public class TreeNode {
 *     int val;
 *     TreeNode left;
 *     TreeNode right;
 *     TreeNode(int x) { val = x; }
 * }
 */
class Solution {
     public List<Integer> rightSideView(TreeNode root) {
        List<Integer> res = new ArrayList<Integer>();
        if(root == null) return res; 
        Queue<TreeNode> q = new LinkedList<TreeNode>();
        q.add(root);
        while(!q.isEmpty())
        {
            int size = q.size();
            for(int i=0; i<size; i++)
            {
                TreeNode curr = q.poll();
                if(i== (size-1))
                {
                    res.add(curr.val);
                }
                if(curr.left!=null)
                {
                    q.add(curr.left);
                }
                   if(curr.right!=null)
                {
                    q.add(curr.right);
                }
            }
        }
        return res; 
    }
}