Terrible LeetCode in Kotlin:
Another day, another LeetCode question (for now). Today, I'm running through #662 Maximum Width of Binary Tree. The problem provides the root of a binary tree, with the expected output being the maximum width between any two nodes of the same level in the tree, including null nodes.
This problem stumped me, and although I did attempt to use BFS initially, I couldn't really figure out a way to satisfy the time constraints with so many potential null nodes.
The solution utilized a very clever trick - within the array representation of a complete tree, the left and right children of a node within a tree will always be at 2i and 2i + 1 respectively, where i is equal to the index of the current node. We can use this trick to hash the imaginary position of the node within a complete tree's array representation, then use the difference in indices to calculate the maximum width.
I work in Kotlin as my LeetCode programming language because my current focus is on Android app development. Kotlin is interoperable with Java, so the solution should be relatively similar albeit with some more boilerplate checks for nulls and such.
Current Grind:
Grind75 list, 22 weeks/16 hours per week, [102/169]
(https://www.techinterviewhandbook.org...)
Chapters:
00:00 - Problem discussion
05:25 - Coding Begins (BFS, Failed Attempt)
30:16 - 2nd Attempt, DFS
39:30 - Solution Discussion (BFS with index hashmap)