Introduction

A Balanced Binary Search Tree (BST) is a type of binary search tree where the height of the tree is minimized, ensuring optimum time complexity for operations such as insertion, deletion, and search. When given a sorted linked list, the challenge is to create a balanced BST from it. This article explains how to achieve this transformation, using both recursive and iterative approaches, while also delving into the underlying concepts and complexities involved.

Concepts

Binary Search Trees

A Binary Search Tree is a binary tree in which each node has a key greater than any key stored in the left subtree and less than any key stored in the right subtree. The main advantage of BST over other data structures is its ability to support efficient search, insertion, deletion, and traversal operations.

Balanced BST

A Balanced BST is a BST with its nodes organized such that the tree height is minimized. Common examples include AVL Trees and Red-Black Trees, which maintain balance using rotations and additional properties for insertions and deletions.

Sorted Linked List

A sorted linked list is a linear data structure where each element is linked to its successor node, and the elements are in non-decreasing order. This structure can be efficiently traversed in a single pass to access each element consecutively.

Creating a Balanced BST from a Sorted Linked List

To convert a sorted linked list into a balanced BST, we must consider the middle element as the root of the BST since it divides the list into two equal halves, ensuring balance.

Recursive Approach

1. Find the Middle Element:
   • Use the slow and fast pointer technique to identify the middle node of the linked list.
   • The slow pointer moves one step at a time, while the fast pointer moves two steps. The slow pointer points to the middle node once the fast pointer reaches the end.
2. Recursive Division:
   • Recursively perform the same operation on the left part of the list for the left subtree and the right part for the right subtree.
   • Base case: If the head is null, return null as the subtree.
3. Construct and Connect Nodes:
   • Create a new tree node with the middle element.
   • Recursively assign the left and right subtrees to this node.

Example

Consider a sorted linked list: 1 -> 2 -> 3 -> 4 -> 5 -> 6 -> 7

• Start: Midpoint is 4, becomes the root.
• Left of 4: List 1 -> 2 -> 3, midpoint 2 becomes left child of 4.
• Right of 4: List 5 -> 6 -> 7, midpoint 6 becomes right child of 4.

Pseudocode

• Convert the linked list to an array for direct access to elements at any index after calculating the size.
• Construct nodes from the array elements, simulating an inorder traversal.
• Repeatedly split the list using indices to mimic the division in recursive technique.
• Use an auxiliary stack or queue to manage nodes yet to be processed.
• Root is 4, left array is [1, 2, 3], right array is [5, 6, 7].
• Continue similar splits recursively using stack-based management.
• Time Complexity: The recursive solution and iterative solution both have $O(N \log N)$ complexity due to the division at each step, with N being the number of nodes. Finding the midpoint for each division costs additional $O(N)$, leading to an overall complexity of $O(N \log N)$.
• Space Complexity: The space complexity is $O(\log N)$ for the recursive stack depth in the recursive approach, and $O(N)$ for the array or stack in the iterative approach.