Cousins in Binary Tree

In a Binary Tree, the root node is at level 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. The following are 2 cousins in a binary tree.

Note:

  1. The number of nodes in the tree will be between 2 and 100.
  2. Each node has a unique integer value from 1 to 100.
/**
 * Definition for a binary tree node.
 * public class TreeNode {
 *     int val;
 *     TreeNode left;
 *     TreeNode right;
 *     TreeNode(int x) { val = x; }
 * }
 */
class Solution {
  boolean xFound, yFound;
  int levelX = 0;
  int levelY = 0;
  TreeNode parentX = null;
  TreeNode parentY = null;

  public boolean isCousins(TreeNode root, int x, int y) {
    dfs(root, x, y, null, 1);
    return (levelX == levelY) && parentX != parentY;
  }

  private void dfs(TreeNode node, int x, int y, TreeNode parent, int depth) {
    if (node == null) return;
    if (xFound && yFound) return;
    if (node.val == x) {
      parentX = parent;
      levelX = depth;
      xFound = true;
    }
    if (node.val == y) {
      parentY = parent;
      levelY = depth;
      yFound = true;
    }
    dfs(node.left, x, y, node, depth + 1);
    dfs(node.right, x, y, node, depth + 1);
  }
}
  • Time Complexity: O(N), where N is the number of nodes in the tree.
  • Space Complexity: O(N).

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out /  Change )

Google photo

You are commenting using your Google account. Log Out /  Change )

Twitter picture

You are commenting using your Twitter account. Log Out /  Change )

Facebook photo

You are commenting using your Facebook account. Log Out /  Change )

Connecting to %s