[C++] Clean Code - DFS Recursion with Explanation

• Imaging how we would find the max height of a tree. We can carry a max-height variable and keep updating it.
With little change we can find the bottom-left as a byproduct of this process.

The idea is to update the bottom-left only when the depth reach to the next level, that is, whenever you need to update max-height when height > max-height;

Find Bottom Left

class Solution {
public:
int findBottomLeftValue(TreeNode* root) {
int bottomLeft = 0;
int height = 0;
dfs(root, 1, height, bottomLeft);
return bottomLeft;
}

private:
void dfs(TreeNode* node, int depth, int& height, int& res) {
if (!node) {
return;
}
if (depth > height) {
res = node->val;    // update res only when redefine the height
height = depth;
}
dfs(node->left, depth + 1, height, res);
dfs(node->right, depth + 1, height, res);
}
};

Find Tree Height
Here is how would you find the height of the tree in this approach, it is very similar to Find The Bottom Left

class Solution {
public:
int treeHeight(TreeNode* root) {
int height = 0;
dfs(root, 1, height);
return height;
}

private:
void dfs(TreeNode* node, int depth, int& height) {
if (!node) {
return;
}
if (depth > height) {
height = depth;
}
dfs(node->left, depth + 1, height);
dfs(node->right, depth + 1, height);
}
};

Looks like your connection to LeetCode Discuss was lost, please wait while we try to reconnect.