DMITRII’s Substack

Share this post

Leetcode daily # 20.04.2023

dmitriisamoilenko.substack.com

Leetcode daily # 20.04.2023

[662. Maximum Width of Binary Tree]

DMITRII SAMOILENKO
Apr 20, 2023
Share
Share this post

Leetcode daily # 20.04.2023

dmitriisamoilenko.substack.com

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

Thanks for reading DMITRII’s Substack! Subscribe for free to receive new posts and support my work.

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)

Thanks for reading DMITRII’s Substack! Subscribe for free to receive new posts and support my work.

Share
Share this post

Leetcode daily # 20.04.2023

dmitriisamoilenko.substack.com
Previous
Next
Comments
Top
New

No posts

Ready for more?

© 2023 DMITRII SAMOILENKO
Privacy ∙ Terms ∙ Collection notice
Start WritingGet the app
Substack is the home for great writing