# Share my concise dfs solution

• ``````/**
* Definition for binary tree with next pointer.
*  int val;
*  TreeLinkNode(int x) : val(x), left(NULL), right(NULL), next(NULL) {}
* };
*/
class Solution {
public:
void dfs(TreeLinkNode *root, int dep) {
if (!root) return;
if (rec[dep]) {
rec[dep]->next = root;
}
rec[dep] = root;
dfs(root->left, dep + 1);
dfs(root->right, dep + 1);
}

dfs(root, 0);
}
};``````

• This is nice and concise, but it uses O(log n) extra space.

• Yes. Is there a way which don't use any extra space?

I also know the bfs solution for this problem but we also need to maintain a queue.

• Yes, but by BFS you can solve it using constant extra space.

I don't know if there is a way to solve it without using any extra space, my guess is no.

• This post is deleted!

• ses O(log n) extra s

Can I ask why it is O(log n), while I see is O(n) space.

• @Acekkkkkkkkk The extra space is due to the hashmap rec, whose size of keys is determined by the depth of the tree, aka log n.

• @cooper Thanks, you are right. But just talk a little bit deeper, I think the worst case is log(n) which is a full binary tree, the best case is O(n) with only one node on each level.

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