Code Destine

Problem Statement

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

Example 

Leftmost value in the last row of first binary tree is 2 and of second binary tree is 6.

Breadth First Search

In Breadth First Traversal, the tree is traversed level by level. Hence to get the result, we have to store the first node value of every level traversal in a variable.

import java.util.LinkedList;
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.right.left = new TreeNode(4);
		node.right.right = new TreeNode(9);

		node.right.left.left = new TreeNode(6);

		int result = main.findBottomLeftValue(node);
		System.out.print(result);
	}

	public int findBottomLeftValue(TreeNode root) {

		Queue<TreeNode> queue = new LinkedList<>();
		queue.add(root);
		int result = root.val;

		int size, i;
		boolean isFirst = true;
		while (queue.size() > 0) {

			isFirst = true;
			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);
				if (isFirst && (root.left != null || root.right != null)) {

					if (root.left != null) {
						result = root.left.val;
					} else {
						result = root.right.val;
					}
					isFirst = false;
				}
			}
		}
		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 left child of every node followed by its right child, while maintaining the level of every child. Once we encountered a new level, we will store the value of the node to a variable.

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

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.right.left = new TreeNode(4);	
		node.right.right = new TreeNode(9);	
		
		node.right.left.left = new TreeNode(6);	
		
		int result = main.findBottomLeftValue(node);
		System.out.print(result);
	}
	
	private int maxLevel = -1;
    private int maxLevelLeftValue = 0;
    
    public int findBottomLeftValue(TreeNode root) {
        findBottomLeft(root, 0);
        return maxLevelLeftValue;
    }
    
    public void findBottomLeft(TreeNode node, int level){
        
        if(node == null) return;
        if(maxLevel < level){
            maxLevel = level;
            maxLevelLeftValue = node.val;
        }       
        findBottomLeft(node.left, level+1);
        findBottomLeft(node.right, level+1);        
    }
	
	public static class TreeNode {		
		int val;
		TreeNode left;
		TreeNode right;
		
		TreeNode(int x) {
			val = x;
		}
	}
}

Result

6

Similar Post

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

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