[Algorithm] Convert Sorted List to Binary Search Tree

Convert Sorted List to Binary Search Tree

Problem Statement

Given a singly linked list where elements are sorted in ascending order, convert it to a height balanced BST.

Solution: DSW alogrithm

Time Complexity : O(n)

Space Complexity : O(1)

This problem is really about using DSW algorithm to convert a backbone to a balanced BST. The main operation is left rotation:

(image from wikipedia, https://en.wikipedia.org/wiki/Tree_rotation)

Each round we will have N/2 backbone nodes we need to do left rotation around. And after each rotation, the remaining backbone nodes are (N - N/2 - 1), the -1 here is always excluding the last element as not a backbone.

Example: [0, 1, 2, 3, 4, 5, 6, 7, 8]

Round 1:

Before:

There are 9 nodes in the backbone, we need N/2 rotation which is 4. So node [0, 2, 4, 6] will be rotated.

After:

Round 2:

There are [1, 3, 5, 7, 8] in the backbone, but we consider the last one as not a backbone. So the real backbone nodes are [1, 3, 5, 7] and to get this we have (N - N/2 - 1). And there are 2 rotations needed at [1, 5].

Round 3:

The remaining backbone nodes, excluding the last one, will be only [1] and the tree is balanced now.

Code Implementation:

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48

class Solution { public: TreeNode* sortedListToBST(ListNode* head) { /* copy a backbone */ ListNode* curr = head; TreeNode* root = NULL; TreeNode* tail = NULL; int count = 0; while (curr) { TreeNode* node = new TreeNode(curr->val); if (root == NULL) { root = node; } else { tail->right = node; } tail = node; curr = curr->next; count++; } count--; /* DSW */ for (int n=count/2; n > 0; n=count/2) { compression(root, n); count = count - n - 1; } return root; } inline void compression(TreeNode*& root, int n) { TreeNode* parent = root; TreeNode* grandparent = NULL; /* left rotate n times */ while (n > 0) { TreeNode* child = parent->right; parent->right = child->left; child->left = parent; if (grandparent) grandparent->right = child; if (grandparent == NULL) { root = child; } grandparent = child; parent = child->right; n--; } } };