How can I find using C if a binary search tree is too tall relatively fast (most of the time)?

To be more specific , lets say I need to find if a tree has a height of at least 10 ,without having to search the whole tree most of the time.

(This is possible because I expect most of the input to be binary search trees which have a heigh greater than 10.)

CodePudding user response：

If there are no preconditions about the structure of the tree, there's no other way but checking one side of the tree, then the other.

int check_depth(struct tree *root, int depth)
{
    if (!root) {
        return 0;
    } else if (depth <= 1) {
        return 1;
    } else {
        return check_depth(root->left,  depth-1) ||
               check_depth(root->right, depth-1);
    }
}

CodePudding user response：

This is an example of a simple algorithm that returns true as soon as it's found a branch longer than 10.

#include <stdbool.h>
#include <stdio.h>

typedef struct _node
{
    int data;
    struct _node *l, *r;
}
node;

node *tree; // some tree
...

bool is_too_tall(node *node, int depth, int max_depth)
{
    if (node == NULL)
        return false;
    if (depth > max_depth)
        return true;
    
    return is_too_tall(node->l, depth   1, max_depth) 
        || is_too_tall(node->r, depth   1, max_depth);
}

int main()
{
    if (is_too_tall(tree, 1, 10))
        puts("Tree is too tall");
}

I think depth first search is the best option for this algorithm (as opposed to breadth first search because it is faster and simpler.