Problem

Given a binary tree, find the deepest node in it.

If there are multiple, return the right most node. (Good to check with the interviewer - some may say left most).

Examples

Example 1:

     1
   /   \
  2     3
 / \   / \
4   5 6   7

Input: root=[1,2,3,4,5,6,7]
Output: 7

Solution

Method 1 - Level Order Traversal

public class Solution {

	public TreeNode findDeepestNode(TreeNode root) {
		if (root == null) {
			return null;
		}

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

		TreeNode current = null;

		while (!queue.isEmpty()) {
			current = queue.poll();

			if (current.left != null) {
				queue.add(current.left);
			}

			if (current.right != null) {
				queue.add(current.right);
			}
		}

		return current; // The last node processed in BFS will be the deepest node
	}
}

Method 2 - Preorder Traversal

Take two global variable as deepestLevel and deepestNode.

We start with level = 0, and increment the level, as we go down. We go to right first, as we want right most child in case of multiple deep nodes.

Code

Java
class Solution {

	private int deepestLevel = 0;

	private TreeNode deepestNode = null;

	public TreeNode findDeepestNode(TreeNode root) {
		dfs(root, 0);
		return deepestNode;
	}

	public void dfs(TreeNode root, int level) {
		if (root == null) {
			return;
		}

		if (level > deepestLevel) {
			deepestNode = root;
			deepestLevel = level;
		}

		// Recurse deeper into the tree
		dfs(root.right, level + 1);
		dfs(root.left, level + 1);
	}
}