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

user_14339566 0
Viewed 308

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.enter image description here

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.

binary-search-tree binary-tree tree search algorithm
2 Answers

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;
}
user_54598390

The following property is very important for solving this question.

Any binary tree node which respects the BST properties will always be searchable using BST Search Algorithm.

Consider the example you had shared.

Tree Image.

Now, suppose

  1. If you are searching for 1 => Then it will lead to success in the first hit. (Count =1)

  2. For 2, it will search in the right subtree of 1. AT 6, no left subtree was found, hence not found.

  3. For 6, search in the right subtree of 1. Match found! (Count =2)

  4. Similarly for 7, search in the right subtree of 1 followed by a search in 6. Match found! (Count =3)

Now, the counter is incremented when all numbers from 0 to max(nodes) are searched in the list.

Another interesting pattern, you can see is that counter is incremented whenever node follows a BST Node property.

One of the important property is:

  • Root node's value is greater than all the root's left's values and less than all the root's right values.

For example, Consider node 7: it is to the right of 6 and right of 1. Hence a valid node.

With this in mind, the problem can be decomposed to Number of valid BST Nodes in a tree.

Solving this is quite straightforward. You try to use a Tree traversal from top to bottom and check if it is in increasing order. If it is not, there is no need to check its children. If it is, then add counter by 1 and check its children.

user_58412970
Related