Educative

Root.left = root.right = root

I’m not understanding the need for this line of code after recursively processing the left and right subtrees… What exactly is the purpose for this?

It seems like a backtracking technique, but I am unable to wrap my head around it.

The following line code is to have the left and right pointers to point to itself.

root.left = root.right = root

We have the root point to itself before passing it to the concatenate_lists function. Because inside the concate function we assign whatever’s in root.left or root.right to tail1 and tail2 and we don’t want tail1 and tail2 to be null as we have not made a check for it when we call on its left and right attributes. You can test it out by comment ing out the above line of code, you will get a compilation error (on python) that the None object has no attribute right on either lines: tail1.right = head2 or tail2.right = head2 as tail1/tail2 is null.

def concatenate_lists(head1, head2):
  if head1 is None:
    return head2
  if head2 is None:
    return head1

  # use left for previous.
  # use right for next.
  tail1 = head1.left
  tail2 = head2.left

  tail1.right = head2
  head2.left = tail1

  head1.left = tail2
  tail2.right = head1
  return head1

You can also declare an entirely new node and point root.right and root.left to it, and the code will work correctly. In short, this line is just there to make sure there are no null nodes in root.left or root.right when passing root to the concatenate_lists functions.