(Saturday) August 13, 2022

Question 199 - Binary Tree Right Side View

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.

Caveats

  1. Check the depth level of the tree
    This is important to add the value to the answer. If we don't know the depth of the tree, end up we only have two situation, which are we add all the value to the answer or the value will overwrite each other.
  2. Always start from the right node Since the question request to view the tree from the right side view, we will be using Preorder or Breadth first search.

Solutions

As you can aware we are tracking depthLevel in both of the solutions. This is ensure we are adding the correct value to the answer.

The next thing you might aware is that, we are using the root.right first instead of root.left. This is to view the node from the right side.

You can try to switch the sequence and check the output.

Preorder Traversal

class Solution {
    public List<Integer> rightSideView(TreeNode root) {
        List<Integer> answer = new ArrayList<>();
        Queue<TreeNode> queue = new LinkedList<>();
        
        dfs(root, answer, 0);
        
        return answer;
    }
    
    private void dfs(TreeNode root, List<Integer> answer, int depthLevel) {
        if (root == null)
            return;
        
        if (answer.size() == depthLevel)
            answer.add(root.val);
        
        dfs(root.right, answer, depthLevel + 1);
        dfs(root.left, answer, depthLevel + 1);
        
        return;
    }
}
class Solution {
    public List<Integer> rightSideView(TreeNode root) {
        Queue<TreeNode> queue = new LinkedList<>();
        List<Integer> answer = new ArrayList<>();
        int depthLevel = 0;
        
        if (root == null)
            return answer;
        
        queue.add(root);
        
        while (!queue.isEmpty()) {
            int size = queue.size();
            
            for (int i = 0; i < size; i++) {
                if (answer.size() == depthLevel) {
                    answer.add(queue.peek().val);
                }
                
                TreeNode left = queue.peek().left;
                TreeNode right = queue.peek().right;
                
                if (right != null)
                    queue.add(right);
                
                if (left != null)
                    queue.add(left);
                
                queue.poll();
            }
            
            depthLevel++;
        }
        
        return answer;
    }
}