Code Destine

Problem Statement

Imagine you are standing on the right side of a binary tree, Write a program to return the values of all the nodes that you can see ordered from top to bottom.

Example 

The right side view of above binary tree shows [3, 20, 7, 1] nodes. 

Breadth First Search

In Breadth First Traversal, the tree is traversed level by level. Hence to get the result, we have to store the extreme right node of every level in the array list.

import java.util.ArrayList;
import java.util.LinkedList;
import java.util.List;
import java.util.Queue;

public class Main {

	public static void main(String[] args) {
		Main main = new Main();

		TreeNode node = new TreeNode(3);
		node.left = new TreeNode(9);
		node.right = new TreeNode(20);	
		
		node.left.left = new TreeNode(2);
		node.left.right = new TreeNode(6);
		
		node.left.left = new TreeNode(15);
		node.right.right = new TreeNode(7);
		
		node.left.left.left = new TreeNode(5);
		node.left.left.right = new TreeNode(8);
		
		node.right.right.right = new TreeNode(1);
		
		List<Integer> result = main.rightSideView(node);
		for(int i : result) {
			System.out.print(i + ",");
		}
	}
	
	public List<Integer> rightSideView(TreeNode root) { 
        
        List<Integer> result = new ArrayList<>();    
        if(root == null) return result;
        
        Queue<TreeNode> queue = new LinkedList<>();
        queue.add(root);
        
        int size, i; 
        while(queue.size() > 0){            
            size = queue.size();
            for(i=0; i<size; i++){                
                root = queue.poll();                
                if(root.left != null) queue.add(root.left);
                if(root.right != null) queue.add(root.right);                
            }
            result.add(root.val);
        }
        return result;
    }
	
	public static class TreeNode {		
		int val;
		TreeNode left;
		TreeNode right;
		
		TreeNode(int x) {
			val = x;
		}
	}
}

Depth First Search

In Depth First Traversal, we will traverse the right child of every node followed by its left child, while maintaining the level of every child. Once we encountered a new level, we will store the value of the node to an array list.

Since we are traversing the right child first, we will always encounter a new level with an extreme right child of that level.

import java.util.ArrayList;
import java.util.List;

public class Main {

	public static void main(String[] args) {
		Main main = new Main();

		TreeNode node = new TreeNode(3);
		node.left = new TreeNode(9);
		node.right = new TreeNode(20);	
		
		node.left.left = new TreeNode(2);
		node.left.right = new TreeNode(6);
		
		node.left.left = new TreeNode(15);
		node.right.right = new TreeNode(7);
		
		node.left.left.left = new TreeNode(5);
		node.left.left.right = new TreeNode(8);
		
		node.right.right.right = new TreeNode(1);
		
		List<Integer> result = main.rightSideView(node);
		for(int i : result) {
			System.out.print(i + ",");
		}
	}
	
	public List<Integer> rightSideView(TreeNode root) {        
        List<Integer> result = new ArrayList<>();
        rightView(root, result, 1);
        return result;
    }
    
    public void rightView(TreeNode node, List<Integer> result, int level){
        
        if(node == null) return;
        
        if(result.size() < level){
            result.add(node.val);
        }        
        rightView(node.right, result, level+1);
        rightView(node.left, result, level+1);
    } 
	
	public static class TreeNode {		
		int val;
		TreeNode left;
		TreeNode right;
		
		TreeNode(int x) {
			val = x;
		}
	}
}

Result

3,20,7,1,

Similar Post

1. PostOrder Traversal of Tree
2. Same Tree
3. Sum of all Left Leaves

That’s all for Binary Tree Right Side View in Java, If you liked it, please share your thoughts in a comments section and share it with others too.