Saturday 24 March 2018

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.

1 comment:

  1. Data Science course is for smart people. Make the smart choice and reach the apex of your career. Learn the latest trends and techniques from the experts.
    data science course

    ReplyDelete