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

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

1
2

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

Solution

Method 1 - Level Order Traversal

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27

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

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26

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);
	}
}