C Language Algorithm – Flatten Binary Tree to Linked List

Today’s algorithm problem is to solve the "Flatten Binary Tree to Linked List" algorithm using C language. Below are my algorithm ideas and implementations. Let's take a look.
Algorithm Problem
Given a binary tree, flatten it to a linked list. The flattened linked list should follow the preorder traversal of the original binary tree.
Algorithm Ideas
We can use recursion to solve this problem. The specific steps are as follows:
Recursively process the left and right subtrees: Recursively flatten the left and right subtrees into linked lists.
Connect the left and right subtrees: Attach the flattened left subtree to the right subtree of the root node, then attach the right subtree to the rightmost node of the flattened left subtree.

👇 Click to receive 👇
👉 C Language Knowledge Resource Collection

Code Implementation

Here is an example code for implementing the "Flatten Binary Tree to Linked List" algorithm in C:
// Definition for a binary tree node.
struct TreeNode {    int val;    struct TreeNode *left;    struct TreeNode *right;};
void flatten(struct TreeNode* root) {    if (!root) return;
    flatten(root->left);    flatten(root->right);
    struct TreeNode* leftSubtree = root->left;    struct TreeNode* rightSubtree = root->right;
    root->left = NULL;    root->right = leftSubtree;
    struct TreeNode* current = root;    while (current->right) {        current = current->right;    }
    current->right = rightSubtree;}
Algorithm Analysis

• Time Complexity: The algorithm visits all nodes of the binary tree, so the time complexity is O(n), where n is the number of nodes in the binary tree.

• Space Complexity: The recursion uses the system stack, so the space complexity is O(h), where h is the height of the binary tree.

Example and Testing

Example

Consider the following binary tree:

    1   / \  2   5 / \   \3   4   6

Flattening it into a linked list gives:

1 \  2   \    3     \      4       \        5         \          6

Testing

#include <stdio.h>#include <stdlib.h>
struct TreeNode {    int val;    struct TreeNode *left;    struct TreeNode *right;};
void printList(struct TreeNode* node) {    while (node) {        printf("%d -> ", node->val);        node = node->right;    }    printf("NULL\n");}
int main() {    // Create a binary tree    struct TreeNode* root = (struct TreeNode*)malloc(sizeof(struct TreeNode));    root->val = 1;    root->left = (struct TreeNode*)malloc(sizeof(struct TreeNode));    root->left->val = 2;    root->left->left = (struct TreeNode*)malloc(sizeof(struct TreeNode));    root->left->left->val = 3;    root->left->right = (struct TreeNode*)malloc(sizeof(struct TreeNode));    root->left->right->val = 4;    root->right = (struct TreeNode*)malloc(sizeof(struct TreeNode));    root->right->val = 5;    root->right->right = (struct TreeNode*)malloc(sizeof(struct TreeNode));    root->right->right->val = 6;
    // Test flatten function    flatten(root);
    // Print the flattened linked list    printList(root);
    // Free memory    // (Memory freeing code omitted here)
    return 0;}

Output:

1 -> 2 -> 3 -> 4 -> 5 -> 6 -> NULL

Conclusion

This article introduces a recursive algorithm to flatten a binary tree into a linked list. By recursively processing the left and right subtrees and connecting the flattened linked lists, we can efficiently solve this problem. The time complexity of this algorithm is O(n), and the space complexity is O(h), which performs well in practical applications.

 Popular Recommendations

• CLion Tutorial – Header File Protection in CLion

• C Language Algorithm – “Path Sum II” Algorithm Problem

• C++ Tutorial – Type Conversion in C++