aboutsummaryrefslogtreecommitdiff
path: root/convert_sorted_bst.c
diff options
context:
space:
mode:
Diffstat (limited to 'convert_sorted_bst.c')
-rw-r--r--convert_sorted_bst.c56
1 files changed, 56 insertions, 0 deletions
diff --git a/convert_sorted_bst.c b/convert_sorted_bst.c
new file mode 100644
index 0000000..8e710c1
--- /dev/null
+++ b/convert_sorted_bst.c
@@ -0,0 +1,56 @@
+// 109. Convert Sorted List to Binary Search Tree
+#include <stdlib.h>
+
+/*
+ * given 'head' of a singly linked list where elements are sorted in ascending
+ * order convert it to a height balanced binary search tree. meaning the depth
+ * of two sub- trees of every node never differs by more than one.
+ */
+
+struct ListNode {
+ int val;
+ struct ListNode *next;
+};
+
+struct TreeNode {
+ int val;
+ struct TreeNode *left;
+ struct TreeNode *right;
+};
+
+int list_len(struct ListNode *head) {
+ struct ListNode *tmp = head;
+ int cnt = 0;
+ while (tmp)
+ cnt++, tmp = tmp->next;
+ return cnt;
+}
+
+struct TreeNode *sortedArrayToBST(int *nums, int n) {
+ if (n <= 0)
+ return NULL;
+ struct TreeNode *root = malloc(sizeof(struct TreeNode));
+ if (n == 1) {
+ root->val = nums[0];
+ root->left = NULL;
+ root->right = NULL;
+ } else {
+ root->val = nums[n / 2];
+ root->left = sortedArrayToBST(nums, n / 2);
+ root->right = sortedArrayToBST(&nums[n / 2 + 1], n - 1 - n / 2);
+ }
+ return root;
+}
+
+struct TreeNode *sortedListToBST(struct ListNode *head) {
+ int n = list_len(head);
+ if (n == 0)
+ return NULL;
+ int *nums = malloc(n * sizeof(int));
+ struct ListNode *tmp = head;
+ for (int i = 0; i < n; i++) {
+ nums[i] = tmp->val;
+ tmp = tmp->next;
+ }
+ return sortedArrayToBST(nums, n);
+}