Find Largest Value in Each Tree Row | Tree Problem | LeetCode 515

4 years ago Lalit Bhagtani 0

Problem Statement

You have given a binary tree, write a program to find out the largest value in each row of a given binary tree.

Example 

Find Largest Value in Each Tree Row

Input : [5, 3, 8, 2, 4, null, 9] Result : [5, 8, 9].

Solution

To solve this problem, we have to find out the largest value at each level. The solution can be implemented using both depth first search and breadth first search algorithm.

Breadth First Search

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(5);
		node.left = new TreeNode(3);
		node.right = new TreeNode(8);		
		node.left.left = new TreeNode(2);
		node.left.right = new TreeNode(4);
		node.right.right = new TreeNode(9);
		
		List<Integer> result = main.largestValues(node);
		result.forEach(System.out::print);
	}
	
	public List<Integer> largestValues(TreeNode root) {
        
        List<Integer> result = new ArrayList<>();        
        if(root == null) return result;
        
        Queue<TreeNode> queue = new LinkedList<>();
        queue.add(root);
        
        int size, i, value;
        while(queue.size() > 0){            
            value = Integer.MIN_VALUE;
            size = queue.size();            
            for(i=0; i<size; i++){                
                root = queue.poll();                
                if(value < root.val){
                    value = root.val;
                }                
                if(root.left != null) queue.add(root.left);
                if(root.right != null) queue.add(root.right);
            }            
            result.add(value);
        }        
        return result;
    }
	
	public static class TreeNode {		
		int val;
		TreeNode left;
		TreeNode right;
		
		TreeNode(int x) {
			val = x;
		}
	}
}

Depth First Search

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(5);
		node.left = new TreeNode(3);
		node.right = new TreeNode(8);		
		node.left.left = new TreeNode(2);
		node.left.right = new TreeNode(4);
		node.right.right = new TreeNode(9);
		
		List<Integer> result = main.largestValues(node);
		result.forEach(System.out::print);
	}
	
	public List<Integer> largestValues(TreeNode root) {        
        List<Integer> result = new ArrayList<>();        
        if(root == null) return result;
        
        dfs(root, 0, result);        
        return result;
    }
    
    public void dfs(TreeNode node, int level, List<Integer> result){
    	
        if(node == null) return;
        
        if(result.size() == level){
            result.add(node.val);
        }else {            
            if(result.get(level) < node.val){
                result.set(level, node.val);
            }
        }
        
        dfs(node.left, level+1, result);
        dfs(node.right, level+1, result);        
    }
	
	public static class TreeNode {		
		int val;
		TreeNode left;
		TreeNode right;
		
		TreeNode(int x) {
			val = x;
		}
	}
}

Result

589

Similar Post

  1. Sum of all Left Leaves
  2. Level Order Traversal of Binary Tree
  3. Minimum Distance Between BST Nodes

That’s all for Find Largest Value in Each Tree Row in Java, If you liked it, please share your thoughts in a comments section and share it with others too.