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);
}
My recursive solution(Java)

Greate recursive! compare with my clumsy and time consuming one.
/** * Definition for binary tree with next pointer. * struct TreeLinkNode { * int val; * TreeLinkNode *left, *right, *next; * TreeLinkNode(int x) : val(x), left(NULL), right(NULL), next(NULL) {} * }; */ class Solution { void dfs(TreeLinkNode* root,TreeLinkNode* p){ 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: void connect(TreeLinkNode *root) { dfs(root,NULL); } };


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); } public void helper(TreeLinkNode left, TreeLinkNode right){ if(left == null  left.next == right) return; // skip repeated subproblems left.next = right; helper(left.left, left.right); helper(left.right, right.left); helper(right.left, right.right); }

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

C++ version:
class Solution { public: void connect(TreeLinkNode *root) { if(root == NULL) return; helper(root>left, root>right); } void helper(TreeLinkNode *node1, TreeLinkNode *node2) { if(node1 == NULL) return; node1>next = node2; helper(node1>left, node1>right); helper(node2>left, node2>right); helper(node1>right, node2>left); } };


A iterative solution
public void connect(TreeLinkNode root){ if (null == root){ return; } Queue<TreeLinkNode> queue = new LinkedList<>(); queue.offer(root); queue.offer(null); while (!queue.isEmpty()){ TreeLinkNode visit = queue.poll(); 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.

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

My DFS version
public class Solution { public void connect(TreeLinkNode root) { helper(root, new ArrayList(), 0); } public void helper(TreeLinkNode root, List<TreeLinkNode> list, int depth) { if (root == null) { return; } if (depth == list.size()) { list.add(root); } else { TreeLinkNode pre = list.get(depth); pre.next = root; list.set(depth, root); } helper(root.left, list, depth + 1); helper(root.right, list, depth + 1); } }