LeetCode Entry

662. Maximum Width of Binary Tree

20.04.2023 medium 2023 kotlin

We can do BFS and track node positions.

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 substack

Join me on Telegram

https://t.me/leetcode_daily_unstoppable/186

Intuition

For every node, positions of it’s left child is \(2x +1\) and right is \(2x + 2\) leetcode_tree.gif

Approach

We can do BFS and track node positions.

Complexity

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