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.
Input:
15 --level 1
/ \
10 35 --level 2
/ \
30 45 --level 3
Output: 15 10 30
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:
// class to construct each node of tree
class Node
{
int data;
Node left,right;
public Node(int data)
{
this.data=data;
left=null;
right=null;
}
}
/* Class to print the left view and construct Tree*/
public class Tree
{
Node root;
static int max_level = 0;
// recursive function to print left view
void leftViewHelper(Node node, int current_level)
{
// Base Case
if (node == null)
return;
// If this is the first node of its level
if (max_level < current_level) {
System.out.print(" " + node.data);
max_level = current_level;
}
// Recur for left and right subtrees
leftViewHelper(node.left,current_level + 1);
leftViewHelper(node.right,current_level + 1);
}
// A wrapper over Helper Function
void leftView()
{
leftViewHelper(root, 1);
}
public static void main(String args[])
{
/* creating a binary tree and entering the nodes */
Tree tree = new Tree();
tree.root = new Node(15);
tree.root.left = new Node(10);
tree.root.right = new Node(35);
tree.root.right.left = new Node(30);
tree.root.right.right = new Node(45);
tree.leftView();
}
}
Output:
15 10 30
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:
import java.util.*; //To use Queue interface implemented using Linked List Class
public class LeftView
{
// Binary tree node
static class Node //Inner Class
{
int data;
Node left,right;
public Node(int data)
{
this.data = data;
this.left = null;
this.right = null;
}
}
// function to print right view of binary tree
static void leftView(Node root)
{
if (root == null)
return;
Queue<Node> q = new LinkedList<>();
q.add(root); //we add the root first.
while (!q.isEmpty())
{
// number of nodes at current level
int count = q.size();
// Traverse all nodes of current level
for (int i = 0; i < count; i++)
{
Node curr = q.poll(); //current node
// Print the left most element at
// the level
if (i == 0)
System.out.print(curr.data + " ");
// Add left child node to queue
if (curr.left != null)
q.add(curr.left);
// Add right child node to queue
if (curr.right != null)
q.add(curr.right);
}
}
}
// Driver code
public static void main(String[] args)
{
// construct binary tree as shown in
// above diagram
Node root = new Node(15);
root.left = new Node(10);
root.right = new Node(35);
root.right.left = new Node(30);
root.right.right = new Node(45);
System.out.println("The Left View of Binary Tree is : ");
System.out.println();
leftView(root);
}
}
Output:
The Left View of Binary Tree is: 15 10 30
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.
The post Left View of Binary Tree in Java appeared first on The Crazy Programmer.
from The Crazy Programmer https://ift.tt/3qpngsq
Comments
Post a Comment