993.cousins-in-binary-tree.md

993. Cousins in Binary Tree

BFS

• Find x and y:
  • In the same level?
    • Yes: Has different parent?
      • Yes: Return true
      • No: Return false
    • No: Return false
  • At the different level: Return false
• Return false

There is an alternative way to check, we traverse each node as parent, and check if their children are x and y.

fun isCousins(root: TreeNode?, x: Int, y: Int): Boolean {
    if (root == null) return false
    val queue = ArrayDeque<TreeNode>()
    val parentMap = HashMap<TreeNode, TreeNode>()
    queue.addLast(root)
    while (queue.isNotEmpty()) {
        val size = queue.size
        var xNode: TreeNode? = null
        var yNode: TreeNode? = null
        repeat (size) {
            val node = queue.removeFirst()
            if (node.`val` == x) xNode = node
            if (node.`val` == y) yNode = node
            if (node.left != null) {
                    queue.addLast(node.left)
                    parentMap[node.left] = node
            }
            if (node.right != null) {
                queue.addLast(node.right)
                parentMap[node.right] = node
            }
        }
        if (xNode != null && yNode != null) {
            if (parentMap[xNode] != parentMap[yNode]) return true
            else return false
        } else if (xNode != null || yNode != null) {
            return false
        }
    }
    return false
}

• Time Complexity: O(n)
• Space Complexity: O(n)

DFS

We traverse the tree to find x and y by DFS, then we store their parents and levels. After traversing, we check if they have the different parents and the same level.

data class NodeInfo(
    val node: TreeNode?,
    val parent: TreeNode?,
    val level: Int
)

private var xNode: NodeInfo? = null
private var yNode: NodeInfo? = null

fun isCousins(root: TreeNode?, x: Int, y: Int): Boolean {
    if (root == null) return false
    dfs(root, x, y, null, 0)
    if (xNode != null && yNode != null) {
        if (xNode!!.level == yNode!!.level && xNode!!.parent != yNode!!.parent) return true
    }
    return false
}

private fun dfs(root: TreeNode?, x: Int, y: Int, parent: TreeNode?, level: Int) {
    if (root == null) return
    if (root.`val` == x) {
        xNode = NodeInfo(
            root, parent, level
        )
    }
    if (root.`val` == y) {
        yNode = NodeInfo(
            root, parent, level
        )
    }
    dfs(root.left, x, y, root, level + 1)
    dfs(root.right, x, y, root, level + 1)
}