Convert Binary Search Tree to Sorted Doubly-Linked List

Convert a BST to a sorted circular doubly-linked list in-place. Think of the left and right pointers as synonymous to the previous and next pointers in a doubly-linked list.

A circular doubly-linked list. Think of the left and right pointers in a tree as synonymous to the previous and next pointers in a list.

The idea is using in-order traversal set previous visited node's left node points to current node, and current node's right node points to previous visited node.

How do we set head's left points to last and the last's right points to head? We just need to keep the head node and let it's left points to the current node, and current node's right points to the head node.

edge case: root node only, we need to point left and right to root itself.

    public void convertBST(TreeNode root) {
        if (root==null) {
            return;
        }

        //root only node
        if (root.left==null&&root.right==null) {
            root.left = root;
            root.right = root;
            return;
        }

        convertBST(root, new TreeNode[1], new TreeNode[1]);
    }

    private void convertBST(TreeNode root, TreeNode[] pre, TreeNode[] head) {
        if (root==null) {
            return;
        }

        convertBST(root.left, pre, head);    
        if (pre[0]==null) {
            head[0]=root;
        } else {
            root.left = pre[0];
            pre[0].right = root;
        }
        TreeNode rightNode = root.right;
        //As soon as the recursion ends, the head will points to the last element and the last one will point to the first element.
        head[0].left = root;
        root.right = head[0];    
        pre[0] = root;
        convertBST(rightNode, pre, head);
    }