BST Construction: Building from Ordered Data

Convert Sorted Array to Binary Search Tree (LeetCode 108)

Strategy: Use Divide and Conquer. Pick the middle element as the current root and recursively construct the left and right subtrees. This naturally results in a height-balanced tree.

public TreeNode sortedArrayToBST(int[] nums) {
    return build(nums, 0, nums.length - 1);
}

private TreeNode build(int[] nums, int low, int high) {
    if (low > high) return null;
    
    // Choose midpoint to keep left/right subtrees balanced
    int mid = low + (high - low) / 2;
    TreeNode node = new TreeNode(nums[mid]);
    
    node.left = build(nums, low, mid - 1);
    node.right = build(nums, mid + 1, high);
    return node;
}

Convert Sorted List to Binary Search Tree (LeetCode 109)

Use Fast and Slow Pointers to find the linked list's midpoint, then use Divide and Conquer.

public TreeNode sortedListToBST(ListNode head) {
    if (head == null) return null;
    if (head.next == null) return new TreeNode(head.val);
    
    ListNode slow = head, fast = head, previous = null;
    // Find midpoint (slow) and track the previous node to disconnect the list
    while (fast != null && fast.next != null) {
        previous = slow;
        slow = slow.next;
        fast = fast.next.next;
    }
    
    // Disconnect the left half from the middle
    previous.next = null;
    
    TreeNode root = new TreeNode(slow.val);
    root.left = sortedListToBST(head);
    root.right = sortedListToBST(slow.next);
    return root;
}

Convert BST to Greater Tree (LeetCode 538)

Update every node's value to its original value plus the sum of all larger nodes.
Strategy: Perform a Reverse In-order traversal (Right $\rightarrow$ Root $\rightarrow$ Left) while maintaining a running total.

private int runningSum = 0;

public TreeNode convertBST(TreeNode root) {
    if (root == null) return null;
    
    // Since we want sums of LARGER nodes, visit Right subtree first
    convertBST(root.right);
    
    runningSum += root.val;
    root.val = runningSum;
    
    convertBST(root.left);
    return root;
}

BST to Doubly Circular Linked List

Transform a BST into its in-order doubly linked list using prev and head pointers.

private TreeNode previousNode = null;
private TreeNode headNode = null;

public TreeNode treeToDoublyList(TreeNode root) {
    if (root == null) return null;
    inorderTraversal(root);
    
    // Connect tail and head to form a circular list
    headNode.left = previousNode;
    previousNode.right = headNode;
    return headNode;
}

private void inorderTraversal(TreeNode current) {
    if (current == null) return;
    
    inorderTraversal(current.left);
    
    if (previousNode != null) {
        previousNode.right = current;
    } else {
        headNode = current; // Smallest node found
    }
    current.left = previousNode;
    previousNode = current;
    
    inorderTraversal(current.right);
}

Construction Strategy Summary