Different views of a Binary Tree: Left View and Right View of a Binary Tree using Breadth First Traversal technique(Part 1):
In this part we will be discussing about the Breadth First Traversal of a binary tree. After that we will be continuing with left view and right view of a binary tree in O(n) time and O(n) space using breadth first traversal technique. The discussion is learning with hands on session wherein you learn by trying it yourself.
There can be two approaches to solve this problem :
(i) Breadth First Traversal approach
(ii) Depth First Approach or Recursive approach
we will talk only about the breadth first approach in this article.
First of all ,we will deep dive into detailed explanation of breadth first traversal technique using queues. Then we will see how we can get the left view and right view from it.
Breadth First Traversal :
We will look into the Breadth First Traversal or Level Order Traversal which is traversing the tree level by level rather than going deep in a branch as we do in a Depth First Traversal .
The breadth first traversal of the binary tree is as follows
level 1 — —>10
level 2 — — >20, 30
level 3 — — >40, 50
You can try the simple breadth first traversal or level order traversal in the given leetcode question in the provided link.
The following is solution to the above question and also the code for Breadth First Traversal with explanation in java:
class Solution {
public List<List<Integer>> levelOrder(TreeNode root) {
List<List<Integer>> ans = new ArrayList();
/* we make a use of queue to note the children of the nodes
currently in the queue */
Queue<TreeNode> q = new LinkedList<TreeNode>();
if(root==null) return ans;
/* Intially queue will be empty so add the root which is the
level 1 element in the queue */
q.add(root);
/* until queue contains elements the while loop will run.*/
while(q.size()!=0)
{
/* Storing size of queue so that elements of a particular
level can be traversed. variable siz is the value of
number of elements at each level */
int siz =q.size();
/* creating list for storing elements of each level */
List<Integer> list = new ArrayList<>();
/* traversing each level */
for(int i=0;i<siz;i++)
{
/* traversing each node of a level */
TreeNode current=q.poll();
/* adding element of each level to the list */
list.add(current.val);
/* checking node for children if present then added
to the queue */
if(current.left!=null)
{
q.add(current.left);
}
if(current.right!=null)
{
q.add(current.right);
}
}
/* adding list of elements of each level to the final
list */
ans.add(new ArrayList(list));
}
return ans;
}
}Time Complexity
The time Complexity of above code is O(n) where n is the number of nodes in the binary tree since we traverse each and every node of binary tree once.
Space complexity
The Space complexity of above code will be O(b) where b is the maximum number of elements in a level. O(b) is the space complexity because we require a queue of maximum b+1 element since at a time maximum b+1 element can be in the queue because if parent is removed at the same time amaximum of its 2 children can be added at maximum which is b-1+2 .
Left View and Right View of Binary Tree:
Left View of Binary Tree:
The first element of each level in a breadth first traversal or level order traversal is the left view of the binary tree. Here is the left view of a binary tree formed from the first element of each level.
a, b, d, h
Practice this question here on geeks for geeks in the provided link:
below is the step by step solution to the problem
class Tree
class Tree
{
void leftView(Node root)
{
if(root==null) return;
/* we make a use of queue to note the children of the nodes
currently in the queue */
Queue<Node> q = new LinkedList<Node>();
/* Intially queue will be empty so add the root which is the
level 1 element in the queue */
q.add(root);
/* until queue contains elements the while loop will run.*/
while(q.size()!=0)
{
/* Storing size of queue so that elements of a particular
level can be traversed siz is the value of number of
elements at each level */
int siz= q.size();
/* traversing each level and adding its children to the
queue */
for(int i=0;i<siz;i++)
{
/* traversing each node of a level */
Node currptr= q.poll();
/* checking node for children if present then children
are added to the queue */
if(currptr.left!=null) q.add(currptr.left);
if(currptr.right!=null) q.add(currptr.right);
/*For the left side view only the first element of each
level is taken */
if(i==0)
System.out.print(currptr.data+" ");
}
}
}
}Right View of Binary Tree:
The Last element of each level in a breadth first traversal or level order traversal is the Right view of the binary tree. Here is the right view of a binary tree formed from the last element of each level.
a, c, g, j
For practice try this question on leetcode in the link given below :
Below is the detailed solution for the same :
class Solution {
public List<Integer> rightSideView(TreeNode root) {
if(root==null) return new ArrayList();
ArrayList<Integer> a = new ArrayList<Integer>();
/* we make a use of queue to note the children of the nodes
currently in the queue */
Queue<TreeNode> q = new LinkedList<TreeNode>();
/* Intially queue will be empty so add the root which is the
level 1 element in the queue */
q.add(root);
/* until queue contains elements the while loop will run.*/
while(q.size()!=0)
{
/* Storing size of queue so that elements of a particular
level can be traversed siz is the value of number of
elements at each level */
int siz= q.size();
/* traversing each level and adding its children to the
queue */
for(int i=0;i<siz;i++)
{
/* traversing each node of a level */
TreeNode currptr= q.poll();
/* checking node for children if present then added to
the queue */
if(currptr.left!=null) q.add(currptr.left);
if(currptr.right!=null) q.add(currptr.right);
/*For the right side view only the last element of each
level is taken */
if(i==siz-1)
a.add(currptr.val);
}
}
return a;
}
}Time Complexity
The time Complexity of above code is O(n) which is same as Breadth First Traversal. For explanation please refer Breadth First Traversal.
Space Complexity
The time Complexity of above code is O(n) which is same as Breadth First Traversal. For explanation please refer Breadth First Traversal.
— — — — — — — — — — — — — — — — — — — — — — — — — —
Hope you like the tutorial. Part 2 is coming soon in which we will be talking about the top view and bottom view of a tree in O(n) time and O(n) space complexitites. please share. And also if you are intrested in gaming stuff so please check it out as well :
by my friend Umer.
