Sometimes we need to find a path that match a particular criteria. The criteria can vary:
- find paths in a tree with node sum equal to K
- find paths in a tree with node sum larger than K
- find paths in a tree with node sum smaller than K
- find paths in a tree that contain a particular node value
- find paths in a tree that don't contain a particular node value
- find a path in a tree that has smallest sum
- find paths in a tree that has largest sum
- find paths in a tree that is the longest
- find paths in a tree that is the shortest
- find the height of a tree
- find paths in a tree that has the same sum
- find paths in a tree that contains a particular sequence
These problem has very similar solutions using pre-order traversal. We need a Collection to store the matching paths, we also need a List to remember the path that leads to the current node.
Whenever we visits a new node, we add the node into the list. We keep visit the left then right branch, until reached leaf node. Once we reached the leaf, we check matching criteria, then copy the matching list into another list and add into the collection. Once we are done with the current node, we remove the current node from the list and return.
BTree.java
The time complexity is dominant by the pre-order traversal which is O(N) and the space complexity is proportional to the size of the List plus the size of the collection, which are O(N) as well.
