LeetCode 653 Learning Experience

Today, while doing binary tree exercises, I came across LeetCode problem 653 (link here). It was originally a relatively simple problem, but when I looked up the solution, I saw a very creative way to solve it. It’s a very clever way to use double pointers when searching a binary tree, so I’d like to share it here.

In short, the question is whether it is possible to find two nodes in a search binary tree so that the sum of the node values ​​is a given number K.

The Author gives the second way:
Original Link is Here.

Quick Explanation of Deque

• Deque = double-ended queue. In Java, ArrayDeque is a common implementation.
• You can add/remove from both ends:
  • addLast(x) → push to the back (like stack push).
  • pollLast() → pop from the back (like stack pop).
  • peekLast() → look at the back (like stack top).
• In this solution, Deque is used purely as a stack (LIFO).

The following are what I learned from the new approach to this problem. The most important feeling is that I used to use double pointers to find two numbers in a sorted array, but now I use double pointers to find two nodes in a tree. It feels like the knowledge I have learned and used has “evolved”.

Key Takeaways

1) Two complementary approaches

• HashSet: the most straightforward implementation with the shortest code, but requires O(n) space.
• Two iterators (BST two-pointers): leverages the BST’s sorted property, using two stacks to simulate ascending and descending iterators. This reduces extra memory to O(h), where h is the tree height.

2) “Two pointers” is not flattening the tree

• The left stack always maintains the path for the ascending inorder iterator (from the smallest upwards).
• The right stack always maintains the path for the descending reverse-inorder iterator (from the largest downwards).
• Each advancement works like this: pop current → switch to the proper subtree → traverse to the extreme (left or right) while pushing the path.
  • Ascending: pop → go to right subtree → push the entire left chain.
  • Descending: pop → go to left subtree → push the entire right chain.

3) Iterator boundary condition

• The main loop condition is often written as left.val < right.val (or left != right) to ensure the same node is not reused.
• Even if the BST contains duplicate values, the algorithm is safe as long as the two nodes are distinct.

4) Time and space complexity

• Both methods visit each node at most twice → O(n) time.
• Space usage:
  • HashSet: O(n).
  • Two iterators: O(h) (close to log n for balanced trees).