Convert Binary Search Tree to Sorted Doubly Linked List

Problem

Convert Binary Search Tree to Sorted Doubly Linked List

Approach

The problem is to convert a binary search tree to a doubly linked list. According to the description, it needs the in-order of the tree and with the order, try to linked these element together. We can use Depth First Search to implement this during the Pop-up opration.

Code

/**
 * Definition of TreeNode:
 * public class TreeNode {
 *     public int val;
 *     public TreeNode left, right;
 *     public TreeNode(int val) {
 *         this.val = val;
 *         this.left = this.right = null;
 *     }
 * }
 */

public class Solution {
    // return {A, B, C, D}
    // A is the left most node in the left subtree
    // B is the right most node int the right subtree
    // C is the left most node int the right subtree
    // D is the right most node int the right
    private TreeNode[] dfs(TreeNode root){
        if(root == null){
            return new TreeNode[4];
        }
        if(root.right == null && root.left == null){
            return new TreeNode[]{root, root, root, root};
        }
        TreeNode[] left = dfs(root.left);
        TreeNode[] right = dfs(root.right);
        root.left = left[3];
        if(left[3] != null){
            left[3].right = root;
        }
        root.right = right[0];
        if(right[0] != null){
            right[0].left = root;
        }
        if(root.left==null){
            return new TreeNode[]{root, root, right[0], right[3]};
        } else if(root.right == null){
            return new TreeNode[]{left[0], left[3], root, root};
        }
        return new TreeNode[]{left[0], left[3], right[0], right[3]};
    }
    /**
     * @param root: root of a tree
     * @return: head node of a doubly linked list
     */
    public TreeNode treeToDoublyList(TreeNode root) {
        TreeNode[] ans = dfs(root);
        if(ans[0] != null)
            ans[0].left = ans[3];
        if(ans[3] != null)
            ans[3].right = ans[0];
        return ans[0];
    }
}