Binary Search Trees

A. Binary Search Tree Implementation

Problem Analysis

The key consideration in this problem is that the input may contain duplicate elements, but these duplicates should not appear in the output binary tree traversal sequences. This detail is not explicit mentioned in the problem statement.

Code Implementation

#include <cstdio>

struct TreeNode {
    int value;
    TreeNode *leftChild;
    TreeNode *rightChild;
};
int nodeCount;

void insertNode(TreeNode *&root, int x) { // Note the reference to pointer
    // Find insertion point
    if (root == NULL) {
        root = new TreeNode;
        root->value = x;
        root->leftChild = root->rightChild = NULL;
        return;
    }
    if (x == root->value) return; // Skip duplicates
    else if (x < root->value) {
        insertNode(root->leftChild, x);
    } else {
        insertNode(root->rightChild, x);
    }
}

TreeNode* buildTree() {
    int tempValue;
    TreeNode *root = NULL;
    for (int i = 0; i < nodeCount; i++) {
        scanf("%d", &tempValue);
        insertNode(root, tempValue);
    }
    return root;
}

void preOrderTraversal(TreeNode *root) {
    if (root == NULL) return;
    printf("%d ", root->value);
    preOrderTraversal(root->leftChild);
    preOrderTraversal(root->rightChild);
}

void inOrderTraversal(TreeNode *root) {
    if (root == NULL) return;
    inOrderTraversal(root->leftChild);
    printf("%d ", root->value);
    inOrderTraversal(root->rightChild);
}

void postOrderTraversal(TreeNode *root) {
    if (root == NULL) return;
    postOrderTraversal(root->leftChild);
    postOrderTraversal(root->rightChild);
    printf("%d ", root->value);
}

int main() {
    while (scanf("%d", &nodeCount) != EOF) {
        TreeNode *root = buildTree();
        preOrderTraversal(root);
        printf("\n");
        inOrderTraversal(root);
        printf("\n");
        postOrderTraversal(root);
        printf("\n");
    }
    return 0;
}
</cstdio>

B. Binary Search Tree Comparison

Problem Analysis

A binary tree can be uniquely determined by its in-order traversal combined with either pre-order or post-order traversal. For binary search trees with the same elements, the in-order traversal will always be identical. However, different binary search trees can be distinguished by they pre-order traversals. Therefore, we can determine if two binary search trees are identical by comparing their pre-order traversals.

Code Implementation

#include <cstdio>
#include <vector>
#include <iostream>
#include <string>
using namespace std;

struct TreeNode {
    int value;
    TreeNode *leftChild;
    TreeNode *rightChild;
};

void insertNode(TreeNode *&root, int x) {
    if (root == NULL) {
        root = new TreeNode;
        root->value = x;
        root->leftChild = root->rightChild = NULL;
        return;
    }
    if (x <= root->value) {
        insertNode(root->leftChild, x);
    } else {
        insertNode(root->rightChild, x);
    }
}

TreeNode* createTreeFromString(const string& data) {
    TreeNode *root = NULL;
    for (int i = 0; i < data.length(); i++) {
        insertNode(root, data[i] - '0');
    }
    return root;
}

// Pre-order traversal
void preOrderTraversal(TreeNode *root, string &s) {
    if (root == NULL) return;
    s += to_string(root->value);
    preOrderTraversal(root->leftChild, s);
    preOrderTraversal(root->rightChild, s);
}

// In-order traversal
void inOrderTraversal(TreeNode *root, string &s) {
    if (root == NULL) return;
    inOrderTraversal(root->leftChild, s);
    s += to_string(root->value);
    inOrderTraversal(root->rightChild, s);
}

int main() {
    int testCases;
    string inputString;
    string pre1, pre2, in1, in2;
    
    while (scanf("%d", &testCases)!=EOF && testCases != 0) {
        cin >> inputString;
        TreeNode *root = createTreeFromString(inputString);
        preOrderTraversal(root, pre1);
        inOrderTraversal(root, in1);
        
        while (testCases--) {
            pre2.clear();
            in2.clear();
            cin >> inputString;
            root = createTreeFromString(inputString);
            preOrderTraversal(root, pre2);
            inOrderTraversal(root, in2);
            
            if (pre1 == pre2 && in1 == in2) 
                printf("YES\n");
            else 
                printf("NO\n");
        }
    }
    return 0;
}
</string></iostream></vector></cstdio>