CareerCup

can you please explain the distance ? thank you

Something in these lines. But it gives me an incorrect output

var allNodes =[];
  function NodeClass(value){

      this.value = value;


  }

   var  root = new NodeClass(20);
   root.left = new NodeClass(8);
   root.right = new NodeClass(22);
   root.left.left = new NodeClass(4);
   root.left.right = new NodeClass(12);
   root.left.right.left = new NodeClass(10);
   root.left.right.right = new NodeClass(14);
   var target = root.left.right;

   function printkdistanceNodeDown(root,  k) {
       // Base Case
       if (root == null || k < 0)  return;

       // If we reach a k distant node, print it
       if (k==0)
       {
         //  console.log(root.value);
           allNodes.push(root.value)
           return;
       }


       // Recur for left and right subtrees
       printkdistanceNodeDown(root.left, k-1);
       printkdistanceNodeDown(root.right, k-1);
   }

   function printkdistanceNode(root, target ,  k) {
       // Base Case 1: If tree is empty, return -1
       if (root == null) return -1;

       
       if (root == target)
       {
           printkdistanceNodeDown(root, k);
           return 0;
       }

       // Recur for left subtree
       var dl = printkdistanceNode(root.left, target, k);

       // Check if target node was found in left subtree
       if (dl != -1)
       {
           
           if (dl + 1 == k){
               console.log(root.value);
               allNodes.push(root.value);
           }

           
           else
               printkdistanceNodeDown(root.right, k-dl-2);

           
           return 1 + dl;
       }

       
       var dr = printkdistanceNode(root.right, target, k);
       if (dr != -1)
       {
           if (dr + 1 == k){
               console.log(root.value);
               allNodes.push(root.value);

           }

           else
               printkdistanceNodeDown(root.left, k-dr-2);
           return 1 + dr;
       }

       
       return -1;
   }

    console.log(printkdistanceNode(root, target, 2));

The expected answer is 4, 20. I get 2,20 :(

sorry, it is not java script (it is c#), but the idea is in code, you can translate it into java script.
In function I don't use parameter "rootNode". It is because my class "BSTNode" contains reference to parent node.
If it is not allowed, then to obtain parent node just create method with input parameters "rootNode" and "currentNode", and then it will be necessary to change only 1 line in below code as follows:
foreach ( var item in new[] { node.GetRightChild(), node.GetLeftChild(), GetParent( rootNode, node ) } ) {

using System.Collections.Generic;

namespace BST {

    public static class NodesFinder<T> {

        public static BSTNode<T>[] FindNodes( BSTNode<T> rootNode, BSTNode<T> initNode, int distance ) {

            var listOfStartNodes = new List<BSTNode<T>> { initNode };
            var excList = new List<BSTNode<T>>();

            for ( int i = 0; i < distance; i++ ) {
                var inclList = new List<BSTNode<T>>();

                foreach ( var node in listOfStartNodes ) {
                    excList.Add( node );
                    var nearestNodes = new List<BSTNode<T>>();

                    foreach ( var item in new[] { node.GetRightChild(), node.GetLeftChild(), node.GetParent() } ) {
                        if ( item == null || excList.Contains( item ) ) { continue; }
                        nearestNodes.Add( item );
                    }
                    inclList.AddRange( nearestNodes );
                }
                listOfStartNodes = inclList;
            }
            return listOfStartNodes.ToArray();
        }
    }
}

By the definition "Printing all nodes at distance k from a given node" is the general for any graph, we can use a modified version of BFS where we keep track of the level as we goes. For particular, we insert -1 (or null as a indicator) when a complete level is push onto the queue. In the case of BST we only have a maximum of two node for the first level and maximum of 4 nodes for the second level (assumption that we start from root). Otherwise if we start from any node, we just need to remember to add parent, left and right as we expand the search tree, when we reach the desire level we can stop.

Just do a BFS with tracking depth as we goes along. Store the node to return if the depth is at desired k-th level. As soon as we start processing k+1-th, we can just stop as we has seen all the k-th level node. We can modified the queue to hold the Node and the depth and pushing start node as

(node, 0)

. When ever you pop and node and pushing it child we push

(node, parent.depth + 1)