C++ recursive solution (beats 100%) with basic explanation

  • 8

    Idea is simple:
    Keep track of the depth of the tree as you move along. Once you get out of left and right subtree of a node, update the leftVal. Code is quite self explanatory. I have added some basic documentation. I hope that it helps!

    class Solution {
        void findBottomLeftValue(TreeNode* root, int& maxDepth, int& leftVal, int depth) {
            if (root == NULL) {
            //Go to the left and right of each node 
            findBottomLeftValue(root->left, maxDepth, leftVal, depth+1);
            findBottomLeftValue(root->right, maxDepth, leftVal, depth+1);
            //Update leftVal and maxDepth
            if (depth > maxDepth) {
                maxDepth = depth;
                leftVal = root->val;
        //Entry function
        int findBottomLeftValue(TreeNode* root) {
            int maxDepth = 0;
            //Initialize leftVal with root's value to cover the edge case with single node
            int leftVal = root->val;
            findBottomLeftValue(root, maxDepth, leftVal, 0);
            return leftVal;

  • 0

    Thanks your idea, here is my Python version with the same idea

    class Solution(object):
        def helper(self, root, level):
            if not root:
                return None
            self.helper(root.left, level + 1)
            self.helper(root.right, level + 1)
            if level > self.max_level:
                self.max_level = level
                self.left_val = root.val
        def findBottomLeftValue(self, root):
            :type root: TreeNode
            :rtype: int
            self.helper(root, 1)
            return self.left_val

  • 0

    my straightforward c++, dfs

    class Solution {
        int findBottomLeftValue(TreeNode* root) {
            pair<int,int> result(root->val,1); //root!=null
            return result.first;
        void dfs(TreeNode* root,int height,pair<int,int>& res)
            if(!root->left && !root->right && height>res.second)
                res = make_pair(root->val,height);
            if(root->left) dfs(root->left,height+1,res);
            if(root->right) dfs(root->right,height+1,res);

Log in to reply

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