How to find the deepest path from root made up of only 1's in a binary search tree?

Question

We have a binary tree (not a BST) made up of only 0s and 1s. we need to find the deepest 1 with a path from root made up only of 1's

Source : Amazon interview Q

Answer 1

public static int findMaxOnesDepth(Node root){

        if(root != null && root.getValue() == 1){
                 return Math.max(1 + findMaxOnesDepth(root.getLeft()), 
                          1 + findMaxOnesDepth(root.getRight());
        }
        else {
            return 0;
        }
}

If the node you are on is a '0', then the depth of '1's is 0. Otherwise, if the node you are on is a '1', then add 1 to the maximum 'one's depth' of both your left and right children - and return the maximum of those.

The above code finds the length, to find the actual nodes along the path, you could use a list to keep track of this

public static ArrayList<Node> findLongestOnesPath(Node root){

       ArrayList<Node> currStack = new ArrayList<Node>();

      if( root != null && root.getValue() == 1){

          currStack.add(root);

          ArrayList<Node> leftStack = findLongestOnesPath(root.getLeft());
          ArrayList<Node> rightStack = findLongestOnesPath(root.getRight());

          if(leftStack.size() > rightStack.size()){
                currStack.addAll(leftStack);
          }
          else{
              currStack.addAll(rightStack);
          }

      }

      return currStack;
}