Swift: Using Depth-First Search for LeetCode Problems
Algorithms in Swift
--
Before we start
Depth-first search for trees is commonly used for LeetCode challenges, even those rated as Medium or above on the platform.
Prerequisites
To follow along with this piece, you should be able to create a binary tree using insertions (although a simple implementation is shown below).
It would be helpful to be familiar with the concept of recursion, and the solution makes use of Swift’s inout parameters
Keywords and Terminology
Root node: The first node in a tree data structure Tree: A data structure with a root value and left and right subtrees
Using DFS for the sample tree
This is a recursive process going on here. This particular implementation of DFS will follow the algorithm, after starting at the root node (this represents an inorder traversal):
- explore left subtree
- traverse (print out) the node
- explore right subtree
Each exploration as described in that algorithm is itself an example of the inorder traversal.
A sample implementation is featured here, and is ready to go in a Playground (you can download an alternative version from the Repo.
LeetCode
LeetCode has a new problem this week:
1625. Lexicographically Smallest String After Applying Operations
Now Lexicographically means the alphabetical order, for example if we have an array ["ap", "apply", "apple"] a sorted array should produce ["apple", "apply", "ap"].
