Left View of a Binary Tree in Java

Solving using Recursion in Preorder Traversal

We can solve the problem to find the left view of the binary tree using Recursion in a preorder traversal. We can solve this problem using consistent space and time. The thought is to navigate the tree in preorder traversal and keep up with the maximum level visited up until now. If the current level is more than the maximum level called up until now, then, at that point, the current hub is the primary hub of the current level, and we print it and update the last level to the current level. 

Algorithm 

For this approach, we will use a maxLevel variable to keep track of the level visited till now. The recursive calls made while visiting nodes, leftView(node.left, level + 1) are called before leftView(node.right, level + 1) to ensure that the left sub-tree for any node of that node is visited before the right subtree. This ensures that the furthest left node is visited at any level before different nodes at that level. Let’s see how we can use this approach to find the left view of a binary tree.

Pseudocode:

int maxLevel = -1 // initialization of maxLevel
leftView(TreeNode* Node,int level) // first call will be to root node and 0
  if(node == NULL) 
    return
  if maxLevel<level
    print node->value
    maxLevel=level
    leftView(node->left,level+1)
    leftView(node->right,level+1)

Implementation in Java

import java.util.*;

public class Main {

    public static class Node {
        int data = 0;
        Node left = null;
        Node right = null;

        Node(int data) {
            this.data = data;
        }
    }

    static int idx = 0;
    static int max_level = 0;
    public static Node create_Tree(int[] arr) {
        if (idx == arr.length || arr[idx] == -1) {
            idx++;
            return null;
        }

        Node node = new Node(arr[idx++]);

        node.left = create_Tree(arr);
        node.right = create_Tree(arr);

        return node;
    }

    public static void leftView(Node node, int level) {
         if (node == null) 
             return; 

         if (max_level < level) { 
             System.out.print(node.data + " "); 
             max_level = level; 
         } 

        leftView(node.left, level + 1); 
        leftView(node.right, level + 1); 
    }

    public static void viewSet(Node root) {
        leftView(root,1);
    }

    public static void solve() {
        int[] arr = { 10, 20, 30, -1, -1, 40, -1, -1, 50, 60, 70, -1, -1, 80, 90, -1, -1, -1, 100, -1, -1 };
        System.out.println("Using Recursion Method");
        Node root = create_Tree(arr);
        viewSet(root);
    }

    public static void main(String[] args) {
        solve();
    }
}

You can also try this code with Online Java Compiler

Run Code

OUTPUT

Using Recursion Method

10 20 30 70 90

Time Complexity: The time complexity for the above algorithm which is used to find the left view of a binary tree is O(N), where N is the number of nodes in the binary tree as the function traverses the tree.

Space Complexity: The space complexity of the algorithm which is used to find the left view of a binary tree is O(H), where H is the height of the binary tree.In the case of skewed trees, the height of the tree can become N which gives a worst of O(N).

Frequently Asked Questions

What is a Binary Tree?

 A generic tree with at most two child nodes for each parent node is known as a Binary Tree. An empty tree is also considered a valid Binary Tree. 

What is the left view of a Binary Tree?

The set of nodes visible when a tree is viewed from the left is known as the left view of a Binary Tree.  

What is the time complexity of Level Order Traversal to view the left view of a binary tree?

The time complexity of a level order traversal is O(N), where N is the number of vertices in the tree.

Conclusion

In this blog, we learned the left view of a binary tree and how we can use different approaches to solve the problem.

• The first approach was to use level order traversal and a queue. In this approach, the queue was used for the traversal of the tree and check if the elements are present. The approach is also known as an iterative approach because, after the traversal of the nodes, a NULL pointer is assigned to mark the end of the level. To do the level order traversal, we then iterate from the first level to the last level and push the children of the nodes in the queue.
   
• The second approach was to use recursion to solve the problem in a preorder traversal. In this approach, we used a maxLevel variable to keep track of the level visited till now. The recursive calls which were made while visiting nodes, leftView(node.left, level + 1) are to be called before leftView(node.right, level + 1) to ensure that for any node, the left sub-tree of that node is visited before the right subtree. This ensures that at any level, the furthest left node is visited before different nodes at that level.
   

If you want to learn about finding the right view of a binary tree, we have a separate article that covers the approaches used to solve the problem. Do give it a read.

Recommended Reading:

• Binary Tree vs Binary Search Tree
• Binary Tree Postorder Traversal
• Boundary Traversal of Binary Tree
• Right View of Binary Tree
• Top View of the Binary Tree | Part 1
• Top View of the Binary Tree | Part 2
• Types of Binary Trees
• BFS v/s DFS For Binary Trees
• Height of Binary Tree

Also check out some of the Guided Paths on topics such as Data Structure and Algorithms, Competitive Programming, etc. as well as some Contests, Test Series, Interview Bundles, and some Interview Experiences curated by top Industry Experts only on Coding Ninjas Studio.

Visit here to learn more about trees. And practice similar problems on Coding Ninjas Studio. If you liked this blog, share it with your friends.