Identifying the two pointer pattern
The two-pointer technique can solve some specific types of binary search tree problems. These are generally easy or medium problems in which we need to traverse the nodes in a binary search tree in the sorted and reverse-sorted order simultaneously until some terminating condition is reached. We may also have a function f that determines whether we should move ahead in the forward and/or reverse direction. If the problem statement or its solution follows the generic template below, it can be solved by applying the sorted traversal technique.
Template:
Given a binary search tree, traverse the nodes simultaneously in the sorted and reverse sorted order until some terminating condition is reached. Process the nodes in each iteration, and based on the output of some function
f, move ahead in the forward and/or reverse direction. Example
Liking the course? Check our discounted plans to continue learning.