Given a binary search tree, print the path with sum k and minimum hops.
Traverse the tree using DFS and keep track of the current path and its sum.
If the current sum equals k, compare the current path ...read more

Question

Given a binary search tree, print the path with sum k and minimum hops.

Accepted Answer

Given a binary search tree, print the path with sum k and minimum hops.

Traverse the tree using DFS and keep track of the current path and its sum.
If the current sum equals k, compare the current path with the minimum path found so far.
If the current sum is greater than k, backtrack to the previous node and continue traversal.
If the current sum is less than k, continue traversal.
Return the minimum path found.
Time complexity: O(nlogn) for balanced tree, O(n^2) for skewed tree.

Given a binary search tree, print the path which has the sum equal to k and has minimum hops. That is, if there are multiple paths with the sum equal to k then print the path with the minimum number of nodes.