Left View of Binary Tree

Difficulty: EasyAccuracy: 33.74%Submissions: 481K+Points: 2

Given a Binary Tree, return Left view of it. Left view of a Binary Tree is set of nodes visible when tree is visited from Left side. The task is to complete the function leftView(), which accepts root of the tree as argument. If no left view is possible, return an empty tree.

Left view of following tree is 1 2 4 8.

1
/ \
2 3
/ \ / \
4 5 6 7
\
8

Example 1:

Input:
   1
 /  \
3    2
Output: 1 3

Example 2:

Input:

Output: 10 20 40

Expected Time Complexity: O(N).
Expected Auxiliary Space: O(N).

Constraints:
0 <= Number of nodes <= 100
0 <= Data of a node <= 1000

//User function Template for Java

/* A Binary Tree node
class Node
{
    int data;
    Node left, right;

    Node(int item)
    {
        data = item;
        left = right = null;
    }
}

Left View of Binary Tree
Difficulty: EasyAccuracy: 33.74%Submissions: 481K+Points: 2
Given a Binary Tree, return Left view of it. Left view of a Binary Tree is set of nodes visible when tree is visited from Left side. The task is to complete the function leftView(), which accepts root of the tree as argument. If no left view is possible, return an empty tree.

Left view of following tree is 1 2 4 8.

          1
       /     \
     2        3
   /     \    /    \
  4     5   6    7
   \
     8   

Example 1:

Input:
   1
 /  \
3    2
Output: 1 3

Example 2:

Input:

Output: 10 20 40
Expected Time Complexity: O(N).
Expected Auxiliary Space: O(N).

Constraints:
0 <= Number of nodes <= 100
0 <= Data of a node <= 1000
*/
class Tree
{
    //Function to return list containing elements of left view of binary tree.
    ArrayList<Integer> leftView(Node root)
    {
      // Your code here
    //  return  dfs(root, new ArrayList<>(), new HashSet<>(), 0);
       return  dfsOptimized(root, new ArrayList<>(), 0);
    }
    
    
    /* T : O(V) S: O(n) */
    public ArrayList<Integer>  dfs( Node root, ArrayList<Integer> leftView, Set<Integer> levelSet, int level){
        
        if(root==null) return leftView;
        
        if( !levelSet.contains(level) ) {
            leftView.add(root.data);
            levelSet.add(level);
        }
        
        dfs( root.left, leftView, levelSet, level+1);
        return dfs( root.right, leftView, levelSet, level+1);
    }
    
    
    int seen=-1;
        /* T : O(V) S: O(n1 */
     public ArrayList<Integer>  dfsOptimized( Node root, ArrayList<Integer> leftView,  int level){
        
        if(root==null) return leftView;
        
        if( seen < level ) {
            leftView.add(root.data);
            seen=level;
        }
        
        dfsOptimized( root.left, leftView, level+1);
        return dfsOptimized( root.right, leftView, level+1);
    }
}