# My recursive solution(Java)

• ``````public void connect(TreeLinkNode root) {
if(root == null)
return;

if(root.left != null){
root.left.next = root.right;
if(root.next != null)
root.right.next = root.next.left;
}

connect(root.left);
connect(root.right);
}``````

• There questions required: You may only use constant extra space. Recurtion in this case will take more than constant extra space...

• I have thought about this solution, but recursion uses stack, which I guess will take O(logN) space.

• Greate recursive! compare with my clumsy and time consuming one.

``````/**
* Definition for binary tree with next pointer.
*  int val;
*  TreeLinkNode(int x) : val(x), left(NULL), right(NULL), next(NULL) {}
* };
*/
class Solution {
if(!root || !root->left) return;

root->left->next = root->right;
if(p && p->right){
p->right->next = root->left;
dfs(root->left,p->right);
}else{
dfs(root->left,NULL);
}
dfs(root->right,root->left);
}
public:
dfs(root,NULL);
}
};
``````

• Great idea! I love this recursive version, I really do! I did try to come up with a recursive solution, but I was stuck with passing both left and right children to a helper method. Your idea is really brilliant.

• What will the time complexity be using recursion? Is it O(n) to add all the nodes to stack?

• @gnayoaix my solution is exactly the same as yours!

• Here is another O(n) time, O(logn) space recursive solution.

``````    public void connect(TreeLinkNode root) {
if(root == null) return;
helper(root.left, root.right);
}

if(left == null || left.next == right) return;   // skip repeated sub-problems
left.next = right;
helper(left.left, left.right);
helper(left.right, right.left);
helper(right.left, right.right);
}
``````

• This is actually O(1) stack space in most languages as the compilers optimize to reuse the recursive stack. You guys need to look at what is called Tail Recursion. Unfortunately, the Java compiler does not optimize this way.

• @leogogogo I really don't think it is O(n) time. There is repeat calculation in your code.

• C++ version:

``````class Solution {
public:
if(root == NULL) return;
helper(root->left, root->right);
}

if(node1 == NULL) return;
node1->next = node2;
helper(node1->left, node1->right);
helper(node2->left, node2->right);
helper(node1->right, node2->left);
}
};
``````

• @hello_world_ so what is the time complexity as your opinion

• Similar solution:

``````void connect(TreeLinkNode root) {
if (root == null || root.left == null) return;

root.left.next = root.right;
if (root.next != null)
root.right.next = root.next.left;

Stream.of(root.left, root.right).forEach(this::connect);
}
``````

• A iterative solution

``````    public void connect(TreeLinkNode root){
if (null == root){
return;
}

queue.offer(root);
queue.offer(null);

while (!queue.isEmpty()){
if (null != visit){
visit.next = queue.peek();
queue.offer(visit.left);
queue.offer(visit.right);
}else {
queue.offer(null);
if (queue.peek() == null){
break;
}
}
}
}

``````

• @anat By extra space usually it refers to not using any additional data Structure. Though you can clarify this with the Interviewer

• By far the easiest to understand solution (and most elegant)! Bravo!

And if anyone is concerned about implicit stack frame space violating O(1), then since this is tail recursive this can be converted to an iterative solution.

Since it's only implicit O(log n) space, it's really not that space consumptive in the long run anyway.

• Personally I think this is the best solution, but is recursion using constant extra space?
What's the time complexicity here?

• @fahsrouq Space complexicity is logN, so I guess here, it's actually the "height" of the tree?

• My DFS version

``````public class Solution {
helper(root, new ArrayList(), 0);
}
if (root == null) {
return;
}
if (depth == list.size()) {