struct node {
    struct node *left;
    struct node *right;
    int value;
};

bool proverka_l (struct node *nNode, int be)
{
    bool rez = true;

    if (nNode->value >= be)
        return false;
    if (nNode->left)
        rez = proverka_l (nNode->left, be);
    if (rez && nNode->right)
        rez = proverka_l (nNode->right, be);

    return rez;
}

bool proverka_r (struct node *nNode, int be)
{
    bool rez = true;

    if (nNode->value <= be)
        return false;
    if (nNode->left)
        rez = proverka_r (nNode->left, be);
    if (rez && nNode->right)
        rez = proverka_r (nNode->right, be);

    return rez;
}

bool walk (struct node *nNode)
{
    bool rez = true;

    if (nNode->left)
        rez = proverka_l (nNode->left, nNode->value);
    if (rez && nNode->right)
        rez = proverka_r (nNode->right, nNode->value);

    if (rez && nNode->left)
        rez = walk (nNode->left);
    if (rez && nNode->right)
        rez = walk (nNode->right);

    return rez;
}

+-1
  +-2
    +-3
      +-4
        +-5
          +-6

+-6
  +-5
    +-4
      +-3
        +-2
          +-1

+-4
  |-2
  | |-1
  | +-3
  +-5
    +-6

+-3
  |-2
  | +-1
  +-5
    |-4
    +-6