# C++ Simple Solution, Concise Code, O(1) space with Morris Trv

• Simple recursion traversal
O(n) space;
O(n) time;

``````class Solution {
void dfs(TreeNode* cur, int height, pair<int, int>& res) {
if (!cur)
return;
if (height > res.second)
res = {cur->val, height};
dfs(cur->left, height + 1, res);
dfs(cur->right, height + 1, res);
}
public:
int findBottomLeftValue(TreeNode* root) {
pair<int, int> res(0, -1);
dfs(root, 0, res);
return res.first;
}
};
``````

Morris Traversal
Morris Traversal
Get Height by Morris Traversal
O(1) space
O(n) time

``````class Solution {
public:
int findBottomLeftValue(TreeNode* root) {
int height = 0;
pair<int, int> res = {0, -1};
TreeNode* cur = root, *prev = nullptr;
while (cur) {
if (cur->left == nullptr) {
//
if (height > res.second)
res = {cur->val, height};
cur = cur->right;
height++;
} else {
prev = cur->left;
int move = 1;
while (prev->right && prev->right != cur) {
prev = prev->right;
move++;
}
if (prev->right == nullptr) {
prev->right = cur;
//
if (height > res.second)
res = {cur->val, height};
cur = cur->left;
height++;
} else {
prev->right = NULL;
height -= move + 1;
cur = cur->right;
height++;
}

}
}
return res.first;
}
};
``````

• @yong.cao.7731 You are not the really O(1) space, because you are using recursive function, of which space cost increases with the depth of path.

• @ayanami98
Hi, it is O(1) space for the second solution which use Morris Traversal.
For the first solution, it does take O(n) space.

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