LeetCode Entry

1361. Validate Binary Tree Nodes

17.10.2023 medium 2023 kotlin

Is Binary Tree of leftChild[] & rightChild[] valid

1361. Validate Binary Tree Nodes medium blog post substack image.png

Join me on Telegram

https://t.me/leetcode_daily_unstoppable/373

Problem TLDR

Is Binary Tree of leftChild[] & rightChild[] valid

Intuition

There are some examples: image.png

Tree is valid if:

  • all the leafs are connected
  • there is no leaf with more than one in nodes

Approach

For connections check let’s use Union-Find. We also must count in nodes.

Complexity

  • Time complexity: \(O(an)\), a - is for Union-Find search, it is less than 10 for Int.MAX_VALUE nodes, if we implement ranks in Union-Find

  • Space complexity: \(O(n)\)

Code


    fun validateBinaryTreeNodes(n: Int, leftChild: IntArray, rightChild: IntArray): Boolean {
      val uf = IntArray(n) { it }
      val indeg = IntArray(n)
      fun root(x: Int): Int = if (x == uf[x]) x else root(uf[x])
      fun connect(a: Int, b: Int): Boolean {
        if (b < 0) return true
        if (indeg[b]++ > 0) return false
        val rootA = root(a)
        val rootB = root(b)
        uf[rootA] = rootB
        return rootA != rootB
      }
      return (0..<n).all {
        connect(it, leftChild[it]) && connect(it, rightChild[it])
      } && (0..<n).all { root(0) == root(it) }
    }