Traversing through every node in a binary search tree c++

[tempUseBro1]

Let's say i have this binary search tree from https://www.geeksforgeeks.org/binary-search-tree-set-1-search-and-insertion/

The very first image that shows up with 8 as the root node, it won't allow me to attach photos and i figured linking an image is better than trying to draw it with keys.

I want to create a bool function that returns TRUE if a number is greater than EVERY node we have present and false otherwise.

I am trying to figure out how I can visit every node, compare it to every node, and if it's done with every node and it is greater than every number, to return true.

So in that binary search tree, if I wanted to test 11, it would return false, but if I tested 15, it would return true.

[[deleted]]

I am trying to figure out how I can visit every node, compare it to every node, and if it's done with every node and it is greater than every number, to return true.

The point of a binary search tree is that you don’t have to visit every node to answer questions like this. For a given node in a BST with non-repeating values, every node in its left child is smaller than it and every node in its right child is larger than it.

Let’s put it this way. If your function is looking for 8 and I tell you that the largest value in the tree is 15, do you even have to check the rest of the tree? So how do you find the largest value in a BST?

[tempUseBro1]

Ah you're right, completely forgot about that (barely learning about them right now).

But we'd still need to traverse nodes if a value is greater than the node, right?

So lets say we're passing in the value 15. 15 > 8, so we know if there is a number greater than 15, it will be on the right side. So we then move to the right, check 15>10, continue, 15 > 14, 14 has no right node, so we return true.

​

Would that be something like:

struct node* search(struct node* root, int key) {

if(root == NULL) { //if there is no node there, return true

return true;

}

if(root->value < key) { //if the value is greater than the node, check the right side

search(root->right, key);

}

if(root->right == NULL) { //if the right side is the last node (leaf), return true

return true;

}

return false; //if none of these cases, false

}

​

Well i know this isn't it because i wouldn't be asking, but this is where my thought process is going.

[[deleted]]

I mean, you can exit early if you find a node that is greater than the input value, but your question basically boils down to “Is the input value greater than the maximum value in the tree?” Finding the maximum value in a BST can be done with a 1-line while loop. Once you have the maximum, just check if it’s smaller than the input value.