Leetcode daily # 20.04.2023

[662. Maximum Width of Binary Tree]

20.04.2023

662. Maximum Width of Binary Tree medium

fun widthOfBinaryTree(root: TreeNode?): Int =
with(ArrayDeque<Pair<Int, TreeNode>>()) {
    root?.let { add(0 to it) }
    var width = 0
    while (isNotEmpty()) {
        var first = peek()
        var last = last()
        width = maxOf(width, last.first - first.first + 1)
        repeat(size) {
            val (x, node) = poll()
            node.left?.let { add(2 * x + 1 to it) }
            node.right?.let { add(2 * x + 2 to it) }
        }
    }
    width
}

blog post

Join me on Telegram

https://t.me/leetcode_daily_unstoppable/186

Intuition

For every node, positions of it’s left child is 2x+12x+1 and right is 2x+22x+2

Approach

We can do BFS and track node positions.

Complexity

• Time complexity:
  O(n)

• Space complexity:
  O(n)