The Cousins in Binary Tree

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.

Example:

  1
2  3

Node 2 and 3 are not cousins because they share the same parent.

    1
   2 3
  4   5

Node 4 and 5 are cousins because they are of same depth/level and they have different parent.

Check Two Nodes are Cousins using DFS and Recursion

We can Depth First Search (DFS) the entire binary tree and record the depth and the parents for each node. This can be stored using two hash tables e.g. unordered_map in C++.

The time complexity is O(N) and the space complexity is O(N) as well where N is the number of the nodes in the binary tree.

/**
 * Definition for a binary tree node.
 * struct TreeNode {
 *     int val;
 *     TreeNode *left;
 *     TreeNode *right;
 *     TreeNode(int x) : val(x), left(NULL), right(NULL) {}
 * };
 */
class Solution {
public:
    bool isCousins(TreeNode* root, int x, int y) {                     
        dfs(root, NULL, 0);
        return (depth[x] == depth[y]) && (parent[x] != parent[y]);
    }
    
    void dfs(TreeNode* root, TreeNode* p, int d) {
        if (root == NULL) return;
        depth[root->val] = d;
        parent[root->val] = p;
        dfs(root->left, root, d + 1);
        dfs(root->right, root, d + 1);
    }
 
private:
    unordered_map<int, int> depth;
    unordered_map<int, TreeNode*> parent;
};

/**
 * Definition for a binary tree node.
 * struct TreeNode {
 *     int val;
 *     TreeNode *left;
 *     TreeNode *right;
 *     TreeNode(int x) : val(x), left(NULL), right(NULL) {}
 * };
 */
class Solution {
public:
    bool isCousins(TreeNode* root, int x, int y) {                     
        dfs(root, NULL, 0);
        return (depth[x] == depth[y]) && (parent[x] != parent[y]);
    }
    
    void dfs(TreeNode* root, TreeNode* p, int d) {
        if (root == NULL) return;
        depth[root->val] = d;
        parent[root->val] = p;
        dfs(root->left, root, d + 1);
        dfs(root->right, root, d + 1);
    }

private:
    unordered_map<int, int> depth;
    unordered_map<int, TreeNode*> parent;
};

Slightly different implementation below, where we return the depth and parent for a given node in the binary tree, using a pair.

/**
 * 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 {
public:
    bool isCousins(TreeNode* root, int x, int y) {
        pair<int, TreeNode*> a = dfs(root, x, 0, nullptr);
        pair<int, TreeNode*> b = dfs(root, y, 0, nullptr);
        return (a.first == b.first) && (a.second != b.second);
    }
    
private:
    pair<int, TreeNode*> dfs(TreeNode* root, int val, int depth, TreeNode* parent) {
        // if we can't find such node in the tree
        if (root == nullptr) {
            return {0, nullptr}; 
        }
        if (root->val == val) {
            return {depth, parent};
        }
        auto a = dfs(root->left, val, depth + 1, root);
        if (a.first != 0) return a;
        auto b = dfs(root->right, val, depth + 1, root);
        return b;        
    }
};

/**
 * 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 {
public:
    bool isCousins(TreeNode* root, int x, int y) {
        pair<int, TreeNode*> a = dfs(root, x, 0, nullptr);
        pair<int, TreeNode*> b = dfs(root, y, 0, nullptr);
        return (a.first == b.first) && (a.second != b.second);
    }
    
private:
    pair<int, TreeNode*> dfs(TreeNode* root, int val, int depth, TreeNode* parent) {
        // if we can't find such node in the tree
        if (root == nullptr) {
            return {0, nullptr}; 
        }
        if (root->val == val) {
            return {depth, parent};
        }
        auto a = dfs(root->left, val, depth + 1, root);
        if (a.first != 0) return a;
        auto b = dfs(root->right, val, depth + 1, root);
        return b;        
    }
};

If the memory requirement is a bit strict, without allocating two hash maps to store the depths and parents of the Tree Nodes, we can Depth First Search the tree in four runs e.g. checking the depths and parents for both nodes respectively:

/**
 * Definition for a binary tree node.
 * struct TreeNode {
 *     int val;
 *     TreeNode *left;
 *     TreeNode *right;
 *     TreeNode(int x) : val(x), left(NULL), right(NULL) {}
 * };
 */
class Solution {
public:
    bool isCousins(TreeNode* root, int x, int y) {
        TreeNode* leftParent = findParent(root, nullptr, x);
        TreeNode* rightParent = findParent(root, nullptr, y);
        if (leftParent == rightParent) return false;
        int dx = depth(root, 0, x);
        int dy = depth(root, 0, y);
        return dx == dy;
    }
    
private:
    int depth(TreeNode* root, int curDepth, int v) {
        if (root == nullptr) return 0;
        if (root->val == v) {
            return curDepth;
        }
        int x = depth(root->left, curDepth + 1, v);
        if (x > 0) return x;
        return depth(root->right, curDepth + 1, v);
    }
    
    TreeNode* findParent(TreeNode* root, TreeNode* parent, int v) {
        if (root == nullptr) return nullptr;
        if (root->val == v) return parent;
        TreeNode* left = findParent(root->left, root, v);
        if (left != nullptr) return left;
        return findParent(root->right, root, v);
    }
};

/**
 * Definition for a binary tree node.
 * struct TreeNode {
 *     int val;
 *     TreeNode *left;
 *     TreeNode *right;
 *     TreeNode(int x) : val(x), left(NULL), right(NULL) {}
 * };
 */
class Solution {
public:
    bool isCousins(TreeNode* root, int x, int y) {
        TreeNode* leftParent = findParent(root, nullptr, x);
        TreeNode* rightParent = findParent(root, nullptr, y);
        if (leftParent == rightParent) return false;
        int dx = depth(root, 0, x);
        int dy = depth(root, 0, y);
        return dx == dy;
    }
    
private:
    int depth(TreeNode* root, int curDepth, int v) {
        if (root == nullptr) return 0;
        if (root->val == v) {
            return curDepth;
        }
        int x = depth(root->left, curDepth + 1, v);
        if (x > 0) return x;
        return depth(root->right, curDepth + 1, v);
    }
    
    TreeNode* findParent(TreeNode* root, TreeNode* parent, int v) {
        if (root == nullptr) return nullptr;
        if (root->val == v) return parent;
        TreeNode* left = findParent(root->left, root, v);
        if (left != nullptr) return left;
        return findParent(root->right, root, v);
    }
};

However, the above C++ algorithm assumes that both X and Y nodes are existent in the tree, otherwise, they will be counted as cousins, as they have same NULL parents and depth 0 according to the DFS recursion algorithms implemented above!

–EOF (The Ultimate Computing & Technology Blog) —

GD Star Rating
loading...

821 words
Last Post: The Review of cozmo robot from Anki
Next Post: How to Free TCP/UDP Port on Windows Using netstat and taskkill?

The Permanent URL is: The Cousins in Binary Tree

Algorithms, Blockchain and Cloud

The Cousins in Binary Tree

Check Two Nodes are Cousins using DFS and Recursion

Leave a Reply

Check Two Nodes are Cousins using DFS and Recursion

Related posts:

Leave a Reply