Iterative solution to find nodes at distance k from another one

Program.java

// My solution (it passes 7 tests out of 10)

import java.util.*;

class Program {
  // This is an input class. Do not edit.
  static class BinaryTree {
    public int value;
    public BinaryTree left = null;
    public BinaryTree right = null;

    public BinaryTree(int value) {
      this.value = value;
    }
  }
  
  static class BT {
    public int value;
    public BT parent = null;
    public Integer distance = null;
    public BinaryTree left = null;
    public BinaryTree right = null;
    public BT(int value) {
      this.value = value;
    }
  }
  
  
  Set<Integer> m = new LinkedHashSet<>();

  public ArrayList<Integer> findNodesDistanceK(BinaryTree tree, int target, int k) {

    Deque<BT> d = new LinkedList<>();
    ArrayList<Integer> results = new ArrayList<>();
    Map<Integer, ArrayList<Integer>> distance = new LinkedHashMap<>();
    BT b = new BT(tree.value);
    b.left = tree.left;
    b.right = tree.right;
    d.addLast(b);
      
    while(!d.isEmpty()) {
      BT el = d.removeLast();
      if(el.left != null && !m.contains(el.left.value)) {
        BT e = new BT(el.left.value);
        e.parent = el;
        e.left = el.left.left;
        e.right = el.left.right;
        d.addLast(e);
        m.add(el.left.value);
      }
      if(el.right != null && !m.contains(el.right.value)) {
        BT e = new BT(el.right.value);
        e.parent = el;
        e.left = el.right.left;
        e.right = el.right.right;
        d.addLast(e);
        m.add(el.right.value);
      }
      
      if(el.value == target) {
        Deque<BT> v = new LinkedList<>();
        Set<Integer> x = new LinkedHashSet<>();
        v.addLast(el);
        Integer z = 1;
        while (!v.isEmpty()) {
          BT o = v.removeLast();
          System.out.printf("Damn distance: %s\n", o.distance);
          if (o.distance != null) {
            z = o.distance + 1;
          }
          
          if(o.parent != null && !x.contains(o.parent.value)) {
              BT e = new BT(o.parent.value);
              e.parent = o.parent;
              e.left = o.parent.left;
              e.distance = z;
              e.right = o.parent.right;
              v.add(e);
              if(distance.get(z) == null) {
                 distance.put(z, new ArrayList<>(Arrays.asList(e.value)));
                 System.out.printf("Parent else: %s;, %s\n", e.value, z);
              } else {
                ArrayList<Integer> l = distance.get(z);
                System.out.printf("Parent else: %s;, %s\n", e.value, z);
                l.add(e.value);
              }
             
              x.add(e.value);
          }
          if(o.left != null && !x.contains(o.left.value)) {
              BT e = new BT(o.left.value);
              e.parent = o.parent;
              e.left = o.left.left;
              e.distance = z;
              e.right = o.left.right;
              v.add(e);
              if(distance.get(z) == null) {
                 distance.put(z, new ArrayList<>(Arrays.asList(e.value)));
                System.out.printf("Left: %s;, %s\n", e.value, z);
              } else {
                ArrayList<Integer> l = distance.get(z);
                l.add(e.value);
                System.out.printf("Left else: %s;, %s\n", e.value, z);
              }
          
            x.add(e.value);
          }
          if(o.right != null && !x.contains(o.right.value)) {
              BT e = new BT(o.right.value);
              e.parent = o.parent;
              e.left = o.right.left;
              e.distance = z;
              e.right = o.right.right;
              v.add(e);
             if(distance.get(z) == null) {
              distance.put(z, new ArrayList<>(Arrays.asList(e.value)));
               System.out.printf("Right: %s;, %s\n", e.value, z);
              } else {
                ArrayList<Integer> l = distance.get(z);
               System.out.printf("Right else: %s;, %s\n", e.value, z);
               l.add(e.value);
              }
            x.add(e.value);
          }
          x.add(o.value);
        }
        if(distance.get(k) != null) {
          results.addAll(distance.get(k));
        }    
      }
      
      m.add(el.value);
    }
   
    return results;
  }
}

Program2.java

//Exercise Author solution

// Copyright © 2021 AlgoExpert LLC. All rights reserved.


import java.util.*;

class Program {

// This is an input class. Do not edit.


static class BinaryTree {

  public int value;

  public BinaryTree left = null;

  public BinaryTree right = null;

​


  public BinaryTree(int value) {

    this.value = value;

  }

  }

​


static class Pair<U, V> {

  public final U first;

  public final V second;

​


  private Pair(U first, V second) {

    this.first = first;

    this.second = second;

  }

}

​

// O(n) time | O(n) space - where n is the number of nodes in the tree


public ArrayList<Integer> findNodesDistanceK(BinaryTree tree, int target, int k) {

  HashMap<Integer, BinaryTree> nodesToParents = new HashMap<Integer, BinaryTree>();

  populateNodesToParents(tree, nodesToParents, null);

  BinaryTree targetNode = getNodeFromValue(target, tree, nodesToParents);

  return breadthFirstSearchForNodesDistanceK(targetNode, nodesToParents, k);

}

​

public ArrayList<Integer> breadthFirstSearchForNodesDistanceK(


    BinaryTree targetNode, HashMap<Integer, BinaryTree> nodesToParents, int k) {

  Queue<Pair<BinaryTree, Integer>> queue = new LinkedList<Pair<BinaryTree, Integer>>();

  queue.offer(new Pair<BinaryTree, Integer>(targetNode, 0));

​

  HashSet<Integer> seen = new HashSet<Integer>(targetNode.value);

  seen.add(targetNode.value);

​


  while (queue.size() > 0) {

    Pair<BinaryTree, Integer> vals = queue.poll();

    BinaryTree currentNode = vals.first;

    int distanceFromTarget = vals.second;

​


    if (distanceFromTarget == k) {

      ArrayList<Integer> nodeDistanceK = new ArrayList<Integer>();


      for (Pair<BinaryTree, Integer> pair : queue) {

        nodeDistanceK.add(pair.first.value);

      }

      nodeDistanceK.add(currentNode.value);

      return nodeDistanceK;

    }

​

    List<BinaryTree> connectedNodes = new ArrayList<BinaryTree>();

    connectedNodes.add(currentNode.left);

    connectedNodes.add(currentNode.right);

    connectedNodes.add(nodesToParents.get(currentNode.value));

​


  for (BinaryTree node : connectedNodes) {

      if (node == null) continue;

​

      if (seen.contains(node.value)) continue;

​

      seen.add(node.value);

      queue.add(new Pair<BinaryTree, Integer>(node, distanceFromTarget + 1));

    }

  }

​

  return new ArrayList<Integer>();

}

​

public BinaryTree getNodeFromValue(


    int value, BinaryTree tree, HashMap<Integer, BinaryTree> nodesToParents) {

  if (tree.value == value) return tree;

​

  BinaryTree nodeParent = nodesToParents.get(value);

  if (nodeParent.left != null && nodeParent.left.value == value) return nodeParent.left;

​

  return nodeParent.right;

}

​

public void populateNodesToParents(


    BinaryTree node, Map<Integer, BinaryTree> nodesToParents, BinaryTree parent) {


  if (node != null) {

    nodesToParents.put(node.value, parent);

    populateNodesToParents(node.left, nodesToParents, node);

    populateNodesToParents(node.right, nodesToParents, node);

  }

  }

}