Convert Sorted List to Binary Search Tree

/**
 * Definition for singly-linked list.
 * struct ListNode {
 *     int value;
 *     ListNode *nextNode;
 *     ListNode(int x) : value(x), nextNode(NULL) {}
 * };
 *
 * Definition for a binary tree node.
 * struct TreeNode {
 *     int value;
 *     TreeNode *leftChild;
 *     TreeNode *rightChild;
 *     TreeNode(int x) : value(x), leftChild(NULL), rightChild(NULL) {}
 * };
 */
class Solution {
public:
    ListNode* currentHead;
    int getSizeOfList(ListNode* node) {
        ListNode* currentNode = node;
        int count = 0;
        while (currentNode != NULL) {
            currentNode = currentNode->nextNode;
            count += 1;
        }
        return count;
    }
    TreeNode* buildBST(int start, int end) {
        if (start > end) {
            return NULL;
        }
        int middle = (start + end) / 2;
        TreeNode* leftSubTree = this->buildBST(start, middle - 1);
        TreeNode* root = new TreeNode(this->currentHead->value);
        root->leftChild = leftSubTree;
        this->currentHead = this->currentHead->nextNode;
        root->rightChild = this->buildBST(middle + 1, end);
        return root;
    }
    TreeNode* sortedListToBST(ListNode* node) {
        int listSize = this->getSizeOfList(node);
        this->currentHead = node;
        return buildBST(0, listSize - 1);
    }
};

This solution entails a function to convert a sorted singly-linked list into a binary search tree (BST) using C++. The approach optimizes space by using an in-order traversal strategy ensuring that the tree is height-balanced.

• Begin by creating two necessary data structures: ListNode for the linked list and TreeNode for the BST, each structured to contain values and pointers to subsequent nodes or tree children.

• The getSizeOfList function computes and returns the size of the linked list by iterating through each node until the end of the list is reached.

• The buildBST function recursively constructs a binary search tree from the linked list. It:

  • Identifies the middle index of the current segment of the list to ensure a balanced BST by using an in-order traversal.
  • Recursively builds the left subtree using the left half of the list.
  • Creates a root node from the middle of the list.
  • Moves to the next list node.
  • Recursively builds the right subtree using the right half of the list.

• The sortedListToBST function integrates these components:

  1. It calls getSizeOfList to obtain the total number of elements in the list.
  2. Sets a class variable currentHead to the head of the list for global tracking during recursion in buildBST.
  3. Calls buildBST, passing the size calculated minus one (as it's zero-indexed) and zero as the start.
  4. Returns the constructed BST.

This method allows for efficient BST construction by only needing to iterate through the list once, maintaining the sorted order as it populates the tree.

class Solution {
    private ListNode listHead;

    private int getSize(ListNode node) {
        ListNode current = node;
        int count = 0;
        while (current != null) {
            current = current.next;
            count++;
        }
        return count;
    }

    private TreeNode buildBST(int left, int right) {
        if (left > right) {
            return null;
        }

        int midpoint = (left + right) / 2;

        TreeNode leftSubtree = buildBST(left, midpoint - 1);

        TreeNode root = new TreeNode(this.listHead.val);
        root.left = leftSubtree;

        this.listHead = this.listHead.next;

        root.right = buildBST(midpoint + 1, right);
        return root;
    }

    public TreeNode sortedListToBST(ListNode head) {
        int totalSize = getSize(head);
        this.listHead = head;
        return buildBST(0, totalSize - 1);
    }
}

The Java solution provided below outlines an efficient approach to convert a sorted singly linked list into a balanced Binary Search Tree (BST), preserving the order and allowing optimized search, insert, and delete operations. This solution takes advantage of the nature of in-order traversal in BSTs and the sorted characteristic of the linked list.

1. First, determine the size of the given linked list using the getSize(ListNode node) method. This method traverses the entire list to count the elements.
2. Implement the main conversion logic in sortedListToBST(ListNode head) method where the linked list's head is passed as an argument. Here:
   • The total size of the linked list is calculated.
   • Starting from the head of the linked list, a recursive helper function buildBST(int left, int right) is used to build the BST.
3. The buildBST(int left, int right) uses a divide-and-conquer approach:
   • It calculates the midpoint of the current segment of the list to ensure the resulting BST is balanced.
   • Recursively builds the left subtree using the list nodes before the midpoint.
   • Creates the root node using the current listHead value and advances the list head.
   • Recursively builds the right subtree using the nodes after the midpoint.
4. The recursion halts when the base condition (left > right) is met, which indicates that all elements have been incorporated into the BST.

Following the described procedure results in a height-balanced BST, constructed in O(n) time and using O(log n) space due to the recursion stack, providing an optimized space-time complexity balance.

struct ListNode* current;
int calculateSize(struct ListNode* node) {
    struct ListNode* temp = node;
    int count = 0;
    while (temp != NULL) {
        temp = temp->next;
        count++;
    }
    return count;
}
struct TreeNode* listToBST(int start, int end) {
    if (start > end) return NULL;
    int middle = (start + end) / 2;
    struct TreeNode* leftChild = listToBST(start, middle - 1);
    if (current == NULL) return NULL;
    struct TreeNode* treeRoot = malloc(sizeof(struct TreeNode));
    treeRoot->val = current->val;
    treeRoot->left = leftChild;
    current = current->next;
    treeRoot->right = listToBST(middle + 1, end);
    return treeRoot;
}
struct TreeNode* sortedListToBinarySearchTree(struct ListNode* headNode) {
    current = headNode;
    int total = calculateSize(current);
    return listToBST(0, total - 1);
}

This solution outlines how to convert a sorted singly-linked list into a binary search tree (BST) using a C program. Here is a brief summary of the process implemented in the code:

• Calculate Size: First, it calculates the size of the linked list. This function traverses the linked list from the head, counting each node until it reaches the end. The function returns the total number of nodes in the list.

• Conversion Function:

  • The listToBST function is designed for recursive BST construction. It follows the divide and conquer approach, where the middle of the list is chosen as the root, and this process is recursively applied to the sub-lists before and after the middle element to construct the left and right subtrees respectively.
  • This function is sensitive to the linked list’s structure, sequentially accessing its elements through a global pointer current, which initially points to the head of the list.
  • It handles edge cases:
    • If the window defined by start and end indices is invalid (start > end), it returns NULL which signifies no BST node can be constructed from the given sublist.
    • Before creating a new TreeNode, it checks if the current pointer is NULL to avoid accessing null pointers.
    • After setting the node's value from the head of the sub-list, current is moved to the next element in the list.
  • The left child of each node is built from the elements before the middle, and once the node is linked to its left child, the right child is constructed using elements after the middle.

• Sorted List To BST:

  • The primary function initializes current to point to the head of the linked list, and then the list's total size is determined.
  • It calls listToBST with the full range of list indices to build and return the balanced BST.

Optimized for performance and simplicity, this solution efficiently handles the transformation of sorted lists to balanced BSTs, ensuring that each node in the list is visited exactly once, hence achieving linear time complexity relative to the size of the input list. The use of recursion and direct tree construction from list nodes minimizes overhead and maximizes efficiency.

/**
 * Definition for a linked list node.
 * function ListNode(value, nextNode) {
 *     this.val = (value === undefined ? 0 : value);
 *     this.next = (nextNode === undefined ? null : nextNode);
 * }
 */

/**
 * Definition for a binary search tree node.
 * function TreeNode(value, leftChild, rightChild) {
 *     this.val = (value === undefined ? 0 : value);
 *     this.left = (leftChild === undefined ? null : leftChild);
 *     this.right = (rightChild === undefined ? null : rightChild);
 * }
 */

var sortedLinkedListToBST = function (head) {
    var getListSize = function (node) {
        let current = node,
            count = 0;
        while (current !== null) {
            current = current.next;
            count += 1;
        }
        return count;
    };
    var buildBSTFromList = function (start, end) {
        if (start > end) return null;
        let midPoint = Math.floor((start + end) / 2);
        let leftTree = buildBSTFromList(start, midPoint - 1);
        let treeNode = new TreeNode(head.val);
        treeNode.left = leftTree;
        head = head.next;
        treeNode.right = buildBSTFromList(midPoint + 1, end);
        return treeNode;
    };
    let totalSize = getListSize(head);
    return buildBSTFromList(0, totalSize - 1);
};

This solution demonstrates how to convert a sorted linked list into a binary search tree (BST) using JavaScript. The task ensures that the resultant BST maintains the properties of a balanced binary search tree where each node ensures the left child value is less than the parent node, and right child value is greater than the parent node. The approach revolves around a divide-and-conquer strategy.

The process begins by defining two main functions within the sortedLinkedListToBST function. The first function, getListSize, calculates the length of the linked list by iterating through each node until the end is reached.

Once the size of the list is determined, the buildBSTFromList function implements the logic to construct the BST. It uses a recursive strategy:

• The function calculates the middle index of the current list segment.
• It recursively creates the left subtree by taking the segment of the list before the middle index.
• A new tree node is created using the value at the middle.
• The linked list head pointer is moved one step to the right – this ensures nodes are processed in ascending order.
• The right subtree is then recursively created with the segment of the list after the middle.
• The node then links to its left and right children, gradually building up the complete tree structure.

Finally, sortedLinkedListToBST invokes buildBSTFromList, starting with the whole list, and returns the root of the constructed binary search tree.

This method effectively transforms a sorted linked list into a balanced BST with a time complexity mainly governed by the traversal through list nodes and recursive subtree constructions, thus leading to an O(n) complexity where 'n' is the number of nodes in the linked list.

class Solution:

    def calculateSize(self, head: ListNode) -> int:
        current = head
        length = 0
        while current:
            current = current.next
            length += 1
        return length

    def sortedListToBST(self, head: ListNode) -> TreeNode:

        # Determine the size of the list
        total_size = self.calculateSize(head)

        # Recursive function to convert list to BST
        def buildTree(left: int, right: int) -> TreeNode:
            nonlocal head

            # Base case
            if left > right:
                return None

            mid = (left + right) // 2

            # Construct the left subtree
            left_child = buildTree(left, mid - 1)

            # Create the tree node using the current node value
            tree_node = TreeNode(head.val)
            tree_node.left = left_child

            # Move to the next list node
            head = head.next

            # Construct the right subtree
            tree_node.right = buildTree(mid + 1, right)
            return tree_node

        return buildTree(0, total_size - 1)

The solution embodies a Python class named Solution which contains methods to convert a sorted singly linked list into a height-balanced binary search tree (BST). Here's the approach detailed in the provided Python function:

• An auxiliary method calculateSize computes the length of the linked list. This function iterates through the list, incrementing a counter until the end of the list is reached.

• The primary method sortedListToBST performs the conversion from the sorted list to the BST:

  • Initially, calculate the total size of the linked list by invoking calculateSize.
  • Define buildTree, a recursive nested function responsible for constructing the tree. It uses the divide and conquer method:
    • Identify the middle element of the current sublist as the root node to maintain balance in the BST.
    • Recursively construct the left subtree using the elements before the middle element.
    • After creating the left child, assign the current list node's value to the tree node, and move to the next node in the list.
    • Recursively create the right subtree using the elements after the middle element.
  • Once the recursion is set, buildTree initializes the construction by setting the tree building bounds from 0 to total_size - 1.

This approach ensures that the BST constructed is height-balanced, fulfilling the binary search tree properties utilizing the sorted nature of the input list for optimal node placements.