A java program to get path between two nodes in binary tree

pathBetweenTwoNodesInBinaryTree.java

import java.util.*;

public class TreeNode {
  int val;
  TreeNode left;
  TreeNode right;
}

public class Solution{
  public static void main(String[] args){
    // create a binary tree here
    TreeNode bTree = new TreeNode();
    TreeNode nodeA = new TreeNode();
    TreeNode nodeB = new TreeNode();
    
    // TODO: optimize by traversing once, and start 
    // capturing path once we find any one of the nodes
    // until the other is found.
    List pathA = pathToNode(bTree, nodeA);
    List pathB = pathToNode(bTree, nodeB);
    List path = new ArrayList();
    Integer commonParent;

    // find common element in the two arrays and join via that
    // [1,2, 5 ,8]
    // [1, 2, 7, 9]
    // 9 to 8 is  [9, 7, 2, 5, 8]
    for(int i : Collections.reverse(pathA)){
      for(int j : Collections.reverse(pathB)){
        if(i == j){
          commonParent = (Integer) i;
        }
      }
    }

    if(commonParent != null){
      for(int i : Collections.reverse(pathA)){
        if (i != commonParent){
          System.out.print(i + " ");
        }
      }
      ListIterator iter = pathB.listIterator();
      while(iter.hasNext()){
        if(iter.nextIndex() >= pathB.indexOf(commonParent)){
          System.out.print(iter.next() + " ");
        }
      }
    } else {
      System.out.println("Empty path");
    }
  }

  // path to node from root
  public ArrayList[] pathToNode(TreeNode bTree, TreeNode node){
    Stack stk = new Stack();
    Boolean found  = false;
    stk.push(bTree);
    List visited = new ArrayList();
    List path = new ArrayList();
    visited.add(bTree.val);

    // dfs
    while(!found){
      if(stk.empty()){
        break;
      }
      // check if the current node is the one
      // if its not, go to its left child
      // if the left child is visited, go to its right child
      TreeNode current = stk.peek();

      if(current.val == node.val){
        found = true;
        break;
      }
      // visited
      if(visited.contains(current)){
        // go to right
        if (!visited.contains(current.right) && current.right != null){
          stk.push(current.right);
          continue;
        } else {
          stk.pop();
        }
      } else {
        visited.add(current);
      }

      // go left
      if(current.left != null){
        stk.push(current.left);
        continue;
      } else {
        stk.pop();
      }
    }

    //  found a path!
    while(!stk.empty()){
      path.add(stk.push());
    }

    return path;
  }
}