Find the number of nodes in a general binary tree that can be searched using BST searching algorithm

Question

First of all, we know that the searching algorithm of a BST looks like this:

// Function to check if given key exists in given BST.
bool search (node* root, int key) 
{
    if (root == NULL)
        return false;

    if (root->key == key)
        return true;

    if (root->key > key)
        return search(root->left, key);

    else
        return search(root->right, key);

}

This searching algorithm is usually applied in a binary search tree. However, when it comes to a general binary tree, such algorithm may give us wrong results.

The following question has trapped me for quite a long time.

Given a general binary tree, count how many nodes in it can be found using the BST searching algorithm above.

Take the binary tree below as an example. The colored nodes are searchable, so the answer is 3.

Suppose the keys in a tree are unique, and we know the values of all the keys.

My thoughts

I have a naive solution in my mind, which is to call the searching algorithm for every possible key, and count how many times the function returns true.

However, I want to reduce the times of calling functions, and also to improve the time complexity. My intuition tells me that recursion can be useful, but I'm not sure.

I think for each node, we need the information about its parent (or ancestors), therefore I have thought about defining the binary tree data structure as follows

struct node {
    int key;
    struct node* left;
    struct node* right;
    struct node* parent;        // Adding a 'parent' pointer may be useful....
};

I couldn't really figure out an efficient way to tell if a node is searchable, neither can I come up with one to find out the number of searchable nodes. Thus I came here to look for help. A hint will be better than a full solution.

This is my first time asking a question on Stack Overflow. If you think this post needs improvement, feel free to leave a comment. Thanks for reading.

Answer 1

To count the keys that can be found, you should traverse the tree and keep track of the range (low, high) that is implied by the path you took from the root. So when you go left from a node that has key 5, then you should consider that you cannot find any values any more that are greater than 5 (or equal, as that value is already accounted for). If that node's left child node has key 2, and you take a right, then you know that you cannot find any values any more that are less than 2. So your window has at that moment narrowed to (2, 5). If that window becomes empty, than it makes no sense to dig deeper in that direction of the tree.

This is an algorithm you can apply easily using recursion. Here is some code:

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

typedef struct node {
    int key;
    struct node* left;
    struct node* right;
} Node;

Node *create_node(int key, Node *left, Node *right) {
    Node * node = malloc(sizeof(struct node));
    node->key = key;
    node->left = left;
    node->right = right;
    return node;
}

int count_bst_nodes_recur(Node *node, int low, int high) {
    return node == NULL || node->key <= low || node->key >= high ? 0
         : 1 + count_bst_nodes_recur(node->left, low, node->key)
             + count_bst_nodes_recur(node->right, node->key, high);
}

int count_bst_nodes(Node *node) {
    return count_bst_nodes_recur(node, -INT_MAX, INT_MAX);
}

int main(void) {
    // Create example tree given in the question:
    Node *tree = create_node(1,
        create_node(2,
            create_node(4, NULL, NULL),
            create_node(5, NULL, NULL)
        ),
        create_node(6,
            NULL,
            create_node(7, NULL, NULL)
        )
    );

    printf("Number of searchable keys: %d\n", count_bst_nodes(tree)); // -> 3
    return 0;
}