Preorder Traversal Implementation

Implementing preorder traversal for LeetCode requires attention to specific interface requirmeents. The function signature expects dynamically allocated memory for the result array and a pointer to track the number of elements.

int getNodeCount(struct TreeNode* node) {
    if (node == NULL) {
        return 0;
    }
    return getNodeCount(node->left) + getNodeCount(node->right) + 1;
}

void collectPreorder(struct TreeNode* node, int* result, int* index) {
    if (node == NULL) {
        return;
    }
    
    result[*index] = node->val;
    (*index)++;
    
    collectPreorder(node->left, result, index);
    collectPreorder(node->right, result, index);
}

int* preorderTraversal(struct TreeNode* root, int* returnSize) {
    *returnSize = getNodeCount(root);
    
    int* result = (int*)malloc(sizeof(int) * (*returnSize));
    int index = 0;
    
    collectPreorder(root, result, &index);
    return result;
}

Checking Tree Equality

The approach leverages preorder traversal to systematically compare corresponding nodes between two trees. Start by examining the current nodes, then recursively verify the left and right subtrees.

bool areIdentical(struct TreeNode* first, struct TreeNode* second) {
    if (first == NULL && second == NULL) {
        return true;
    }
    
    if (first == NULL || second == NULL) {
        return false;
    }
    
    if (first->val != second->val) {
        return false;
    }
    
    return areIdentical(first->left, second->left) 
        && areIdentical(first->right, second->right);
}

Symmetric Tree Verification

A tree exhibits symmetry when its left and right subtrees mirror eachother. Specifically, the left subtree of the root should correspond to the right subtree of the root in structure and values. Any violation of this mirroring property indicates the tree is not symmetric.

The recursive solution compares corresponding nodes from opposite sides at each level.

bool checkMirror(struct TreeNode* left, struct TreeNode* right) {
    if (left == NULL && right == NULL) {
        return true;
    }
    
    if (left == NULL || right == NULL) {
        return false;
    }
    
    if (left->val != right->val) {
        return false;
    }
    
    return checkMirror(left->left, right->right) 
        && checkMirror(left->right, right->left);
}

bool isSymmetric(struct TreeNode* root) {
    if (root == NULL) {
        return true;
    }
    return checkMirror(root->left, root->right);
}

Subtree Detection

The problem requires determining whether one tree exists as a subtree within another. The solution involves two phases: first, identifying all potential root positions within the larger tree, then verifying tree equality at those positions.

Every node in the main tree represents a potential subtree root, making simple traversal sufficient for candidate identification.

bool areIdentical(struct TreeNode* a, struct TreeNode* b) {
    if (a == NULL && b == NULL) {
        return true;
    }
    
    if (a == NULL || b == NULL) {
        return false;
    }
    
    if (a->val != b->val) {
        return false;
    }
    
    return areIdentical(a->left, b->left) 
        && areIdentical(a->right, b->right);
}

bool isSubtree(struct TreeNode* main, struct TreeNode* target) {
    if (main == NULL) {
        return false;
    }
    
    if (main->val == target->val && areIdentical(main, target)) {
        return true;
    }
    
    return isSubtree(main->left, target) 
        || isSubtree(main->right, target);
}

Binary Tree Construction from Preorder String

This problem involves reconstructing a binary tree from its preorder traversal representation using '#' to indicate null nodes. The input format uses '#' characters for empty positions, following the pattern where each non-null node is followed by its left subtree, then its right subtree.

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

typedef char TreeData;

struct TreeNode {
    TreeData value;
    struct TreeNode* left;
    struct TreeNode* right;
};

struct TreeNode* createNode(TreeData data) {
    struct TreeNode* node = (struct TreeNode*)malloc(sizeof(struct TreeNode));
    if (node == NULL) {
        perror("Memory allocation failed");
        exit(1);
    }
    
    node->value = data;
    node->left = NULL;
    node->right = NULL;
    return node;
}

void inorderDisplay(struct TreeNode* root) {
    if (root == NULL) {
        return;
    }
    
    inorderDisplay(root->left);
    printf("%c ", root->value);
    inorderDisplay(root->right);
}

struct TreeNode* buildTree(TreeData* input, int* position) {
    if (input[*position] == '#') {
        (*position)++;
        return NULL;
    }
    
    struct TreeNode* node = createNode(input[(*position)++]);
    node->left = buildTree(input, position);
    node->right = buildTree(input, position);
    
    return node;
}

int main() {
    char input[100];
    scanf("%s", input);
    
    int pos = 0;
    struct TreeNode* tree = buildTree(input, &pos);
    inorderDisplay(tree);
    
    return 0;
}

Inverting a Binary Tree

Tree inversion involves swapping left and right children at every node. The recursive approach processes subtrees first, then performs the swap at the current node. This ensures children are already inverted before the parent swap occurs.

void performInversion(struct TreeNode* node) {
    if (node == NULL) {
        return;
    }
    
    performInversion(node->left);
    performInversion(node->right);
    
    struct TreeNode* temp = node->left;
    node->left = node->right;
    node->right = temp;
}

struct TreeNode* invertTree(struct TreeNode* root) {
    performInversion(root);
    return root;
}

Balanced Binary Tree Verification

A balanced binary tree maintains the property that for every node, the height difference between its left and right subtrees never exceeds one. The solution requires computing heights for each node while simultaneously checking the balance condition.

int calculateHeight(struct TreeNode* node) {
    if (node == NULL) {
        return 0;
    }
    
    int leftHeight = calculateHeight(node->left);
    int rightHeight = calculateHeight(node->right);
    
    return (leftHeight > rightHeight ? leftHeight : rightHeight) + 1;
}

bool isBalanced(struct TreeNode* root) {
    if (root == NULL) {
        return true;
    }
    
    int leftHeight = calculateHeight(root->left);
    int rightHeight = calculateHeight(root->right);
    
    if (abs(leftHeight - rightHeight) > 1) {
        return false;
    }
    
    return isBalanced(root->left) && isBalanced(root->right);
}