Convert Binary Search Tree to Sorted Doubly Linked List

gistfile1.txt

/*
// Definition for a Node.
class Node {
    public int val;
    public Node left;
    public Node right;

    public Node() {}

    public Node(int _val,Node _left,Node _right) {
        val = _val;
        left = _left;
        right = _right;
    }
};
*/
class Solution {
    public Node treeToDoublyList(Node root) {
      // stopping condition
      if (root == null) {
        return root;
      }
      
      Node leftHead = treeToDoublyList(root.left);
      Node rightHead = treeToDoublyList(root.right);
      
      // Make it circular
      root.left = root;
      root.right = root;
      
      return connect(connect(leftHead, root), rightHead);
    }
  
    private Node connect(Node n1, Node n2) {
      if (n1 == null) {
        return n2;
      }
      
      if (n2 == null) {
        return n1;
      }
        
      // Fix n1 left's right to point to n2, which is the right of top node of n1
      n1.left.right = n2;
      // Fix n2 left's right to point to n1, which is right of the top node of n2
      n2.left.right = n1;
      // Fix n2 left to point to top of n1 points by n1.left
      Node n2Left = n2.left;
      n2.left = n1.left;
      // Fix n1 left to point to top of n2 points by n2.left
      n1.left = n2Left;
      
      return n1;
    }
}