LeetCode #102 — Binary Tree Level Order Traversal
Find more useful articles at www.davidseek.com
LeetCode’s challenge #102 asks us to traverse a Binary Search Tree in level order. Level order traversal is the key to solve a multitude of tech challenges and comes up in many different varieties within numerous questions on LeetCode.
The idea is: We enqueue the root of the tree into a queue. Within a while loop, we dequeue the root and enqueue each child while maintaining the current level.
Our disadvantage using Swift is that the standard library doesn’t come with a native queue implementation. If we were to use an array, we’d get from a linear to a quadratic time complexity. This is because removing the first element of an array is in itself a linear operation because of the need to shift all indices.
In other words: While the loop we need to use to get all nodes from the BST is a linear operation O(n), shifting all indices is also a linear operation O(n) and combined is therefore O(n) * O(n) -> O(n * n) -> O(n^2).
