dfs: O(n) + O(1)

bfs: O(n) + O(n)

public class Solution {
    public void connect(TreeLinkNode root) {
        dfsHelper(root);
    }

    private void dfsHelper(TreeLinkNode node) {
        if (node == null) return;
        if (node.left == null && node.right == null) return;

        node.left.next = node.right;

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

        dfsHelper(node.left);
        dfsHelper(node.right);
    }
}

get rid of helper function

public class Solution {
    public void connect(TreeLinkNode node) {
        if (node == null) return;
        if (node.left == null && node.right == null) return;

        node.left.next = node.right;

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

        connect(node.left);
        connect(node.right);
    }

}

Follow up - what if the given tree could be any binary tree

bfs without queue

public class Solution {
    public void connect(TreeLinkNode root) {
        TreeLinkNode dummyChild = new TreeLinkNode(0);
        TreeLinkNode prevChild = dummyChild;

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

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

            if (root.next != null) root = root.next;
            else {
                prevChild = dummyChild;
                root = dummyChild.next;
                dummyChild.next = null;
            }
        }

    }
}