Left View of Binary Tree in Java

In this article, we look into a problem related to binary tree. Given a binary tree, we have to print its Left View. We will see the different methods to solve this problem with their implementations in java. Along with this, we will also look into the time and space complexities of our methods.

By left of binary tree, we mean the nodes visible to us when the tree is visited from the left side starting from the root. In other words, the nodes which are present at the starting of each level in a binary tree.

Also Read: Right View of Binary Tree in Java

Let us consider this binary tree:

 

The left view of above binary tree will give output: 1 2 4 7.

The nodes are highlighted in the figure. We start from the root node 1 at level 1 then we go down each level printing the first node encountered. At level 2 node 2 is the first node so print it, at level 3 node 4 and at the last level 4 node 7 is the only node.

Note: If a level contains only one node then that node is a part of Left View.

Method 1 (Recursive Approach)

We traverse the tree in Pre-Order fashion keep track of current level by passing a named max_level variable by reference to each recursive call or maintain a static variable so to keep track of it. When we process the current node we check if it’s level is greater than max_ level reached till now. If the current node’s level is greater than the max level we print it and update max level with the current node’s level. Otherwise, we traverse for the Left subtree at first then the right subtrees and continue the execution in the same way.

Below is the implementation of the above approach in Java:

Output:

Time Complexity: We do a traversal of all nodes of the tree in a Preorder fashion so the complexity is O (n).

Space Complexity: We call the function for each node so if System stack space is considered the complexity is O (n).

Method 2 (Iterative Approach Using Queue)

We use standard Level Order Traversal technique. We print the leftmost node at each level. Firstly, We are going to enqueue root node in a Queue of type Node. After this, we enqueue the left child and right child of the current node. Thereafter, while processing each node if it is the first node at that level we print it. If the node is not the first node at that particular level we still add it’s child nodes and continue checking whether each node is the first at it’s level.

Below is the implementation of the above approach in Java:

Output:

Time Complexity: We do level by level traversal of all nodes so here time complexity is O (n).

Space Complexity: The Queue we use to implement the level order traversal will at the most store the nodes present at all levels and if we are given a skewed binary tree then it will store nodes at all levels so the space complexity is O (n).

Comment below in case you have any queries.

Leave a Comment

Your email address will not be published.