1. All Nodes Distance K in Binary Tree

1. All Nodes Distance K in Binary Tree[Microsoft]

This is the first article in this publication and many more will come.
To add swift solution for DS problems in this publication, Ping me to add you as a writer.

To solve this problem, developers need to understand few concepts:

• Binary Tree
• Inorder (Left-Node-Right (LNR)) Traversal or Level Order Tree Traversal
• BFS
• Stack
• Queue

Problem: All Nodes Distance K in Binary Tree

How to Approach this problem?

• Recursive solution
• Iterative solution

We will see the iterative solution in this article, as making it into recursion will be easy once iterative solution is clear.

There are generally two cases for the nodes at a distance of K:

1. Node at a distance K is a child node of the target node.
2. Node at a distance K is the ancestor of the target node.

The idea is to store the parent node of every node in a hash-map with the help of the Level-order traversal on the tree. Then, Simply Traverse the nodes from the Target node using Breadth-First Search on the left-child, right-child, and the parent node. At any instant when the distance of a node the from the target node is equal to K then add all the nodes of the queue in the result.

1. Create private method with responsibility to store the parent node of every node in a hash-map

2. Implement BFS Traversal for traversing the left-child, right-child, and the parent node at each level

3. Find all nodes at K distance from given target node using Step 1 & 2.

Thanks for reading this article, keep learning & growing.

Github: https://github.com/charlieInDen/InterviewQuestions-Swift/