public void connect(TreeLinkNode root) {
if(root==null) return ;
link(root.left,root.right);
}
//HELPER FUNCTION TO LINK TWO NODES TOGETHER
public void link(TreeLinkNode left, TreeLinkNode right){
if(left==null && right==null) return ;
left.next = right;
link(left.left,left.right);
link(left.right,right.left);
link(right.left,right.right);
}
Simple recursive Java solution O(1) space O(n) time


@jedihy I'm not sure what you mean by "space O(n) time". My remark is related to zihao_li stating this is
O(1)
space, when clearly it'sO(n)
space on a generic tree, andO(log n)
on a perfect tree.See this algorithm for a true
O(1)
spaceO(n)
time iterative algorithm which works on any binary tree.

I wrote the same code as yours for the first time, but then I realized this was worse than O(n). Let me explain:
root // \\ left right // \\ // \\ subT1 subT2 subT3 subT4
Every subTree in the graph has a size of n/4, and the size of the whole tree is n.
Then, in order to apply the algorithm on the whole problem, the code first apply it on the first two subtrees, then the two subtrees in the middle, and finally the last two. So, if the total time consumption is T(n), then it's formulated as follows:T(n) = 3T(n/2)+O(1)
This results in T(n) being equal to O(n^(ln3/ln2)). As ln3/ln2>ln2/ln2=1, this algorithm is worse than O(n).
I wrote exactly the same code as yours, but it could not break through 3ms, as many actual O(n) algorithms did. Then I did the analysis above and finally saw why it was coming this way.
