How to find the deepest root path, consisting of only 1 in a binary search tree?

Question

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

Source: Amazon Q interview

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 node you are at '0', then the depth of '1 is 0. Otherwise, if node you are at' 1 ', then add 1 to the maximum' one depth 'of both your left and right children - and return them maximum.

The above code finds the length to find the actual nodes along the path, you can use a list to track 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;
}