1
\$\begingroup\$

Mu solution to Leetcode problem Cousins in Binary Tree works, but the code feels bulky. Is there a better way to solve this problem, particularly to use less additional variables? I will appreciate any suggestions on how to improve this code.

Problem:

In a binary tree, the root node is at depth 0, and children of each depth k node are at depth k+1.

Two nodes of a binary tree are cousins if they have the same depth, but have different parents.

We are given the root of a binary tree with unique values, and the values x and y of two different nodes in the tree.

Return true if and only if the nodes corresponding to the values x and y are cousins.

My code:

/**
* Definition for a binary tree node.
* struct TreeNode {
*     int val;
*     TreeNode *left;
*     TreeNode *right;
*     TreeNode() : val(0), left(nullptr), right(nullptr) {}
*     TreeNode(int x) : val(x), left(nullptr), right(nullptr) {}
*     TreeNode(int x, TreeNode *left, TreeNode *right) : val(x), left(left), right(right) {}
* };
*/

class Solution {
private:
    void is_cousins(TreeNode* root, int to_find, int depth, 
        TreeNode* parent, pair<int, TreeNode*>& pair) {
    
    if (!root)
        return;
    
    is_cousins(root->left, to_find, depth + 1, root, pair);
    is_cousins(root->right, to_find, depth + 1, root, pair);
    
    if (root->val == to_find) {
        pair.first = depth;
        pair.second = parent;
        return;
    }
}

public:
    bool isCousins(TreeNode* root, int x, int y) {
    
        pair<int, TreeNode*> pairx = make_pair(0, nullptr);
        pair<int, TreeNode*> pairy = make_pair(0, nullptr);
    
        is_cousins(root, x, 0, nullptr, pairx);
        is_cousins(root, y, 0, nullptr, pairy);

        if (pairx.first == pairy.first && pairx.second != pairy.second)
            return true;
        return false;
    }
};
\$\endgroup\$
1
  • \$\begingroup\$ Good of you to explicitly state two concerns about your code: 1) bulk 2) amount of additional variables. The second wouldn't enter my mind; but seems about as valid as single assignment. \$\endgroup\$ Commented May 9, 2020 at 4:36

2 Answers 2

Reset to default
2
\$\begingroup\$

My first issue is that this function is badly named.

    void is_cousins(TreeNode* root, int to_find, int depth, 
        TreeNode* parent, pair<int, TreeNode*>& pair)

It has nothing to do with cousins. It is simply finding the depth and parent of a particular value. You should name it appropriateely.

I don't like passing output parameters to a function:

    void is_cousins(TreeNode* root, int to_find, int depth, 
        TreeNode* parent, pair<int, TreeNode*>& pair)

The parameter pair is the output of the function. Why not just return this value. That would be more logical and easier to read.

You don't have a truth state on whether the value x or y are found. I suppose you could say that nullptr in pair is a good way to test this. But that will make things complicated down the road when you try and use this function for other things that are not cousin related; so I don't like that idea. You could used a depth of -1 to indicate failure that would be better.

Talking of default values:

Your current default result is make_pair(0, nullptr) this means you found the root as the value (even if the root value does not equal left of right). This may work for your current situation out of sheer luck but you are returning a bad value.

i.e. A value that is not found in the tree and the root node will both return the same result.

Here is a major ineffeciency.

    is_cousins(root->left, to_find, depth + 1, root, pair);
    is_cousins(root->right, to_find, depth + 1, root, pair);

If you find the value on the left you still search the right subtree. This means you always search the whole tree even if you find the correct node very quickly.

You should check the result of the left search before doing the right search.

This is an anti patten

        if (pairx.first == pairy.first && pairx.second != pairy.second)
            return true;
        return false;

The pattern:

        if (test) {
            return true;
        }
        return false;

        // Can always be simplified to:

        return test;

This is a long handed way of writing:

         return pairx.first == pairy.first && pairx.second != pairy.second;

If you think that is too long for an expression to use in a reurn, then it is too long an expression for any context. In that case you should put the test in a named function so it is obvious what it is doing.

          return are_cousing_nodes_from_Depth(pairx, pairy);

     using DepthInfo = pair<int, TreeNode*>;
     inline bool are_cousing_nodes_from_Depth(DepthInfo const& lhs, DepthInfo const& rhs)
     {
         return lhs.first  == rhs.first    // Same depth
             && lhs.second != rhs.second;  // Not siblings
     }
\$\endgroup\$
1
\$\begingroup\$

Remarks about algorithm:

I see findParentDepth() (my suggestion for "the look-for-single-value method") doing a full traversal. Input specification is tree with unique values:
stop looking on first occurrence.

(If not a single value was found there is no cousin.)

With one value (say, a) found, one condition for no cousins would be the other child holding the other value b: check the right child.

All that might still be needed is a level search for b at the level of a, possibly excluding the part of the tree already traversed.

\$\endgroup\$
1
  • 1
    \$\begingroup\$ I do not yet have an idea how to decently code a level search for b at the level of a excluding the part of the tree already traversed. Not sure, too, of the merits of checking for b in upper levels, immediately exiting when found. \$\endgroup\$ Commented May 9, 2020 at 4:54

You must log in to answer this question.

Start asking to get answers

Find the answer to your question by asking.

Ask question

Explore related questions

See similar questions with these tags.