Binary Tree Implementation with Extended Preorder Input

This C program constructs a binary tree from an extended preorder sequence where missing children are marked with asterisks. It outputs postorder and inorder traversals and counts nodes with two children.

#include <stdio.h>
#include <stdlib.h>

typedef struct TreeNode {
    char value;
    struct TreeNode* left;
    struct TreeNode* right;
} TreeNode;

int doubleChildCount = 0;

TreeNode* buildFromExtendedPreorder() {
    char input;
    scanf("%c", &input);
    
    if (input == '*') {
        return NULL;
    }
    
    TreeNode* newNode = (TreeNode*)malloc(sizeof(TreeNode));
    newNode->value = input;
    newNode->left = buildFromExtendedPreorder();
    newNode->right = buildFromExtendedPreorder();
    return newNode;
}

void printInorder(TreeNode* root) {
    if (root) {
        printInorder(root->left);
        printf("%c", root->value);
        printInorder(root->right);
    }
}

void printPostorder(TreeNode* root) {
    if (root) {
        printPostorder(root->left);
        printPostorder(root->right);
        printf("%c", root->value);
    }
}

void countDoubleChildren(TreeNode* root) {
    if (root) {
        if (root->left && root->right) {
            doubleChildCount++;
        }
        countDoubleChildren(root->left);
        countDoubleChildren(root->right);
    }
}

int main() {
    printf("Enter extended preorder sequence: ");
    TreeNode* root = buildFromExtendedPreorder();
    
    printf("Inorder traversal: ");
    printInorder(root);
    
    printf("\nPostorder traversal: ");
    printPostorder(root);
    
    countDoubleChildren(root);
    printf("\nNodes with two children: %d\n", doubleChildCount);
    
    return 0;
}

Binary Tree Reconstruction from Preorder and Inorder Traversals

This program constructs a binary tree from given preorder and inorder sequences, then outputs the postorder traversal and counts nodes with degree 2.

#include <stdio.h>
#include <stdlib.h>
#include <string.h>

typedef struct BTNode {
    char data;
    struct BTNode* left;
    struct BTNode* right;
} BTNode;

int degreeTwoNodes = 0;

BTNode* reconstructTree(char* pre, char* in, int length) {
    if (length == 0) return NULL;
    
    BTNode* node = (BTNode*)malloc(sizeof(BTNode));
    node->data = pre[0];
    node->left = node->right = NULL;
    
    int rootPos;
    for (rootPos = 0; rootPos < length; rootPos++) {
        if (in[rootPos] == pre[0]) break;
    }
    
    node->left = reconstructTree(pre + 1, in, rootPos);
    node->right = reconstructTree(pre + rootPos + 1, in + rootPos + 1, length - rootPos - 1);
    return node;
}

void postorderTraversal(BTNode* root) {
    if (root) {
        postorderTraversal(root->left);
        postorderTraversal(root->right);
        printf("%c ", root->data);
    }
}

void countDegreeTwo(BTNode* root) {
    if (root) {
        if (root->left && root->right) {
            degreeTwoNodes++;
        }
        countDegreeTwo(root->left);
        countDegreeTwo(root->right);
    }
}

int main() {
    char preSeq[100], inSeq[100];
    int length;
    
    printf("Enter preorder sequence: ");
    scanf("%s", preSeq);
    
    printf("Enter inorder sequence: ");
    scanf("%s", inSeq);
    
    length = strlen(preSeq);
    BTNode* root = reconstructTree(preSeq, inSeq, length);
    
    printf("Postorder traversal: ");
    postorderTraversal(root);
    
    countDegreeTwo(root);
    printf("\nDegree-2 nodes: %d\n", degreeTwoNodes);
    
    return 0;
}

Binary Search Tree Construction and Analysis

This implementation creates a binary search tree from integer input, then outputs preorder and inorder traversals along with tree depth.

#include <stdio.h>
#include <stdlib.h>

typedef struct BSTNode {
    int key;
    struct BSTNode* left;
    struct BSTNode* right;
} BSTNode;

void insertBST(BSTNode** root, int value) {
    if (*root == NULL) {
        *root = (BSTNode*)malloc(sizeof(BSTNode));
        (*root)->key = value;
        (*root)->left = (*root)->right = NULL;
    } else if (value < (*root)->key) {
        insertBST(&(*root)->left, value);
    } else if (value > (*root)->key) {
        insertBST(&(*root)->right, value);
    }
}

void preorderBST(BSTNode* root) {
    if (root) {
        printf("%d ", root->key);
        preorderBST(root->left);
        preorderBST(root->right);
    }
}

void inorderBST(BSTNode* root) {
    if (root) {
        inorderBST(root->left);
        printf("%d ", root->key);
        inorderBST(root->right);
    }
}

int calculateDepth(BSTNode* root) {
    if (root == NULL) return 0;
    
    int leftDepth = calculateDepth(root->left);
    int rightDepth = calculateDepth(root->right);
    
    return (leftDepth > rightDepth ? leftDepth : rightDepth) + 1;
}

int main() {
    BSTNode* root = NULL;
    int input;
    
    printf("Enter integers (Ctrl+D to end): ");
    while (scanf("%d", &input) == 1) {
        insertBST(&root, input);
    }
    
    printf("Preorder: ");
    preorderBST(root);
    
    printf("\nInorder: ");
    inorderBST(root);
    
    printf("\nTree depth: %d\n", calculateDepth(root));
    
    return 0;
}