Given two sorted linked lists. Find the path of maximum sum.

Given two sorted linked lists. You start with a one of the two lists and then move till the end. You may switch to the other list only at the point of intersection (which mean the two node with the same value in different lists.) You have to find the path of maximum sum.

Eg
  1->3->30->90->120->240->511
  0->3->12->32->90->125->240->249
  You can switch at 3 90 or 240 so the max sum paths is
  1->3->12->32->90->125->240->511 

Sol:

This can be solved in O(m+n).

Take two pointers p1 and p2 for both lists. 

Maintain two sums curr1 and curr2 for each list init to 0.

1. If p1 == p2: 
• if curr1 > curr2: Choose LL1 as path upto this point.
• else: Choose LL2 as path.
2. If p1 < p2:
• curr1 += p1
• increment p1 to next node.
3. else if p2 < p1:
• curr2 += p2
• increment p2 to next node
4. if p1 == null:
• traverse all of p2 and keep incrementing curr2.
• Take the path with greater sum
5. if p2 == null: // do as above for p1

https://www.geeksforgeeks.org/flipkart-interview-set-7-sde-ii/

Find all the Nodes at the distance K from a given node in a Binary tree. Print them in any order.

Sol:

This can be divided into two cases:

1. It is easy to print the nodes at distance K from node which are under the subtree of the given node. Pass an integer 'dist' to its children and increment it each time. When 'dist' == K, print those nodes.
2. Nodes at distance K from the given node with its parent node in the path. For this we can return 'dist' in our recursive function. And increment it at each step before returning. When returned value at any point is K we print those nodes. Special case: If we are doing inorder traversal, we need to handle a special case when the given node is the right child of its parent. In this case we will have to traverse the left child of its parent again.

https://www.geeksforgeeks.org/print-nodes-distance-k-given-node-binary-tree/