[Algorithm] Leftmost Deepest Tree Node (Tree/C++)

Problem Link: https://binarysearch.com/room/Graph-Traversers-gi4poVe0pC

This problem is to find the value of the deepest value. If there are multiple such values, return the leftmost one. We can approach this question in two different ways(there’re other ways too): DFS and BFS.

DFS

First, set the initial pair<int,int>p such that p.first=level, p.second=value. As we go down to the deeper level, we keep tracking of the level. When the current level is greater than the p.first, then update the value. As we call dfs(root->left) before dfs(root->right), this would give us the leftmost node at the deepest level.

BFS

The BFS approach is very straightforward. At each level, update the initial value(int res) as the first node at that level.

Both DFS/BFS take O(n) time since we traverse each and every node only once.

[Contact]
✅ Email: changjin9792@gmail.com
✅ Github: https://github.com/JasonLee-cp
️✅ Medium: https://changjin9792.medium.com/