Test if two nodes in a binary search tree are cousins

Question

Cousins are nodes at the same level of the tree, with different parents. They don't have to share the same grandparent.

My solution depends on having a binary search tree with unique elements.

This code is faster than writing a special find(Node *) that returns the node's level and parent, and comparing results for each node. If the nodes are not at the same level, this version will only descend down to the level of the node closer to the top, and bail out early.

I'm looking for confirmation that it is correct.

bool are_cousins(Node *root, Node *a, Node *b)
{
 if (a == b || a == nullptr || b == nullptr) {
 return false;
 }
 Node *a_parent = nullptr;
 Node *b_parent = nullptr;
 Node *a_seek = root;
 Node *b_seek = root;
 while (a_seek != nullptr && b_seek != nullptr) {
 if (a == a_seek && b == b_seek) {
 // found both nodes at the same level
 return a_parent != b_parent;
 }
 if (a == a_seek || b == b_seek) {
 // found one node but not the other at this level. bail out
 return false;
 }
 // found neither. seek down one more level
 a_parent = a_seek;
 a_seek = (a->value < a_seek->value) ?
 a_seek->left : a_seek->right;
 b_parent = b_seek;
 b_seek = (b->value < b_seek->value) ?
 b_seek->left : b_seek->right;
 }
 return false;
}

Answer 1

The logic seems sane to me in general.

If the caller has the values to seek instead of node pointers, then you could change the function parameters to the value types and drop the a == nullptr || b == nullptr checks. But if the caller has node pointers that you cannot know for sure if null or not, then indeed you don't have a choice.

I find these statements more readable without the line breaks and unnecessary parentheses:

a_seek = a->value < a_seek->value ? a_seek->left : a_seek->right;
b_seek = b->value < b_seek->value ? b_seek->left : b_seek->right;

• japreiss: a and a_seek are pointers, so we're only comparing the addresses. This function searches for specific nodes instead of values. You're right, the function could take values instead of node pointers instead, but the fundamental logic would not change.
• janos: You have a point. I rewrote that part.