Question
C++ Fix this balanced binary tree given a singly linked list which has data members sorted in ascending order. The left side of the tree
C++ Fix this balanced binary tree given a singly linked list which has data members sorted in ascending order. The left side of the tree is balanced fine, but the right side of the tree is not.
input: 1 2 3 4 5 6 7 8 9
current preorder output: 5 3 2 1 4 8 7 6 9
expected preorder output: 5 3 2 1 4 7 6 8 9
#include #include /* Link list node */ struct LNode { int data; struct LNode* next; };
struct TNode { int data; struct TNode* left; struct TNode* right; }; struct TNode* newNode(int data); int countLNodes(struct LNode *head); struct TNode* sortedListToBSTRecur(struct LNode **head_ref, int n); struct TNode* sortedListToBST(struct LNode *head) { int n = countLNodes(head); return sortedListToBSTRecur(&head, n); } struct TNode* sortedListToBSTRecur(struct LNode **head_ref, int n) { if (n <= 0) return NULL;
struct TNode *left = sortedListToBSTRecur(head_ref, n/2); struct TNode *root = newNode((*head_ref)->data); root->left = left;
*head_ref = (*head_ref)->next; root->right = sortedListToBSTRecur(head_ref, n-n/2-1); return root; } int countLNodes(struct LNode *head) { int count = 0; struct LNode *temp = head; while(temp) { temp = temp->next; count++; } return count; } void push(struct LNode** head_ref, int new_data) {
struct LNode* new_node = (struct LNode*) malloc(sizeof(struct LNode));
new_node->data = new_data;
new_node->next = (*head_ref);
(*head_ref) = new_node; }
void printList(struct LNode *node) { while(node!=NULL) { printf("%d ", node->data); node = node->next; } }
struct TNode* newNode(int data) { struct TNode* node = (struct TNode*) malloc(sizeof(struct TNode)); node->data = data; node->left = NULL; node->right = NULL; return node; }
void preOrder(struct TNode* node) { if (node == NULL) return; printf("%d ", node->data); preOrder(node->left); preOrder(node->right); }
int main() {
struct LNode* head = NULL; push(&head, 9); push(&head, 8); push(&head, 7); push(&head, 6); push(&head, 5); push(&head, 4); push(&head, 3); push(&head, 2); push(&head, 1); printf(" Given Linked List "); printList(head);
struct TNode *root = sortedListToBST(head); printf(" PreOrder Traversal of constructed BST "); preOrder(root); return 0; }
Step by Step Solution
There are 3 Steps involved in it
Step: 1
Get Instant Access to Expert-Tailored Solutions
See step-by-step solutions with expert insights and AI powered tools for academic success
Step: 2
Step: 3
Ace Your Homework with AI
Get the answers you need in no time with our AI-driven, step-by-step assistance
Get Started