Recursions

Question 1

(Medium) All Nodes Distance K in Binary Tree

We are given a binary tree (with root node root), a target node, and an integer value K.

Return a list of the values of all nodes that have a distance K from the target node. The answer can be returned in any order.

Answer 1

Approach 1:

1. Build. hashmap of parents for every node.
2. Then do BFS on this graph, each node has max 3 children (parent, child1, child2) maintain visited array with dist.

Approach 2.1:

Percolate Distance down & up in the recursion stack. (Sexy Thought).

1. Keep propagating zero down until the target is found and then add+1 and keep propagating down.
2. if node is not the target keep returning zero, and if node is equal to target return 1, and then onwards keep returning +1.

if the returned value is greater than zero repropagate this new value+1 down the stack again for its left and right children. But keep returning +1 to its parent.

https://leetcode.com/problems/all-nodes-distance-k-in-binary-tree/discuss/143886/Java-O(1)-space-excluding-recursive-stack-space.

Approach 2.2:

Good recursion here too.

https://leetcode.com/problems/all-nodes-distance-k-in-binary-tree/solution/