Determine whether a binary tree is a search binary tree and a complete binary tree

Title Description

Given a binary tree with no duplicate nodes, determine whether the binary tree is a search binary tree and a complete binary tree.

Enter a description:

The first line inputs two integers n and root, n for the total number of nodes of the binary tree, and root for the root node of the binary tree.

The following n rows have three integers fa, lch, RCH in each row, indicating that the left son of FA is LCH and the right son is rch. (If LCH is 0, FA has no left son, RCH is the same)

ps:The label of the node is the value of the node

Output description:

The first line outputs whether the binary tree is the answer to the search Binary tree, and if so outputs "true", otherwise outputs "false".

The second line outputs the answer whether the binary tree is a complete binary tree or "true" if it is, or "false" if it is not.

Remarks:

1≤n≤5∗1051 \leq n \leq 5*10^51≤n≤5∗105

1≤fa,lch,rch,root≤n1 \leq fa,lch,rch,root \leq n1≤fa,lch,rch,root≤n

Questions:

Judgement Binary Search Tree: Recursive middle-order traversal is OK. The middle-order traversal of a binary search tree must be ascending. You can save the previous and current nodes of the middle-order traversal for judgment, and exit directly once they are not satisfied

Judging a complete binary tree: proceed according to the following rules:

• Hierarchical traversal, left to right order;
• If the current node has a right son and no left son, return false;
• If the current node is not owned by both left and right sons, then the latter nodes must be leaf nodes, otherwise false is returned.
• Return true

Code:

#include <cstdio>
#include <queue>

using namespace std;

const int N = 500010;

struct BST {
    int lch, rch;
} bst[N];

int n, rt;
int fa, lch, rch;

bool is_bst(int root, int& pre) {
    if (!root) return true;
    if (!is_bst(bst[root].lch, pre)) return false;
    if (pre && pre > root) return false;
    pre = root;
    return is_bst(bst[root].rch, pre);
}

bool is_cbt(int root) {
    if (!root) return true;
    queue<int> q;
    int l, r;
    bool leaf = false;
    q.push(root);
    while (!q.empty()) {
        int now = q.front();
        q.pop();
        l = bst[now].lch;
        r = bst[now].rch;
        if ((leaf && (l || r)) || (!l && r)) return false;
        if (l) q.push(l);
        if (r) q.push(r);
        else leaf = true;
    }
    return true;
}

int main(void) {
    scanf("%d%d", &n, &rt);
    while (n--) {
        scanf("%d%d%d", &fa, &lch, &rch);
        bst[fa].lch = lch;
        bst[fa].rch = rch;
    }
    int pre = 0;
    puts(is_bst(rt, pre) ? "true" : "false");
    puts(is_cbt(rt) ? "true" : "false");
    return 0;
}