Objective: In a Binary Tree, print left view of it
Input: A binary tree.
What is left View of a binary Tree
When just look at the tree from the left side , all the nodes you can see will be the left view of the tree.
Example:
Approach:
Method 1:
- Traverse the tree from left to right
- Print the first node you encounter
- Take two variables , currentLevel=0 and nextLevel=1
- As soon as you change level , change the currentLevel = nextLevel
- Print only when current level<nextLevel so this way you will print only the first element
- For rest of the nodes on the the level currentLevel and nextLevel are equal so it wont print
Method 2:
Do the Level order traversal and print the first node value
Complete Code:
This file contains bidirectional Unicode text that may be interpreted or compiled differently than what appears below. To review, open the file in an editor that reveals hidden Unicode characters.
Learn more about bidirectional Unicode characters
| public class LeftViewOfTree { | |
| public static int index = 0; | |
| public void Method2_levelOrder(Node root) { | |
| int h = height(root); | |
| for (int i = 1; i <= h; i++) { | |
| index = 1; | |
| printLevels(root, i); | |
| // System.out.println(""); | |
| } | |
| } | |
| public void printLevels(Node root, int h) { | |
| if (root == null) | |
| return; | |
| if (h == 1 && index == 1) { | |
| System.out.print(" " + root.data); | |
| index++; | |
| } else { | |
| printLevels(root.left, h – 1); | |
| printLevels(root.right, h – 1); | |
| } | |
| } | |
| public static int currentLevel =0; | |
| public void leftViewRecur(Node root, int nextLevel){ | |
| if(root==null) return; | |
| if(currentLevel<nextLevel){ | |
| System.out.print (" " + root.data); | |
| currentLevel = nextLevel; | |
| } | |
| leftViewRecur(root.left,nextLevel+1); | |
| leftViewRecur(root.right,nextLevel+1); | |
| } | |
| public int height(Node root) { | |
| if (root == null) | |
| return 0; | |
| return 1 + Math.max(height(root.left), height(root.right)); | |
| } | |
| public static void main(String[] args) throws java.lang.Exception { | |
| Node root = new Node(5); | |
| root.left = new Node(10); | |
| root.right = new Node(15); | |
| root.left.left = new Node(20); | |
| root.left.right = new Node(25); | |
| root.right.left = new Node(30); | |
| root.right.right = new Node(35); | |
| root.left.right.right = new Node(45); | |
| LeftViewOfTree i = new LeftViewOfTree(); | |
| System.out.println("METHOD 1: "); | |
| i.leftViewRecur(root, 1); | |
| System.out.println("\nMETHOD 2 : Using Level Order, Left view "); | |
| i.Method2_levelOrder(root); | |
| } | |
| } | |
| class Node { | |
| int data; | |
| Node left; | |
| Node right; | |
| public Node(int data) { | |
| this.data = data; | |
| this.left = null; | |
| this.right = null; | |
| } | |
| } |
Output:
METHOD 1: 5 10 20 45 METHOD 2 : Using Level Order, Left view 5 10 20 45
Please check the height(Node root) method. I think the base case (root == null) should return -1 instead of 0;