REPOSTING SINCE PREVIOUS POST HAD INCORRECT TREENODE DEFINITION

Given a binary search tree with Integer values for the nodes, print all the parents of every leaf node in the tree. Pretty simple question description.

TreeNode Definition :

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

Note : Previous definition I gave had parent pointer incorrectly. There was no parent pointer provided.
Example -

Input : TreeNode Root which is root of the entire BST.
          500
	      /  \
       300    600
        / \
     100  350
         /   \
	  320    360

Answer : 500,300,350
Reason : 500 is parent of leaf 600. 300 is parent of leaf 100. 350 is parent of leaves 320 and 360.

So I was asked this recently at an OCI onsite by a hiring manager and I think my rejection was based on this question solely.
I thought the solution was simple enough where you just visit every node and check whether it's children are leaves. If any one of the children are leaves then print the current node (parent) and continue. This solution would be O(n) time where n is the number of nodes and O(n) space complexity for the recursion stack according to me. You can make a small optimization where you check if the child is a leaf and not recurse into it if it is and then I think the space complexity becomes O(h) where h is the height of the BST.
The interviewer was very rude IMO and asked me whether I know what time and space complexity is. I was not expecting this at all since I couldnt think of anything wrong with my solution. I couldnt think of a way to know if a node is a leaf without visiting it and you would have to repeat for every node in the tree.
Another solution is to traverse the tree and build a parent-child map but that would once again be O(n) for both complexities.
I tried thinking of whether there was any BST property I could use but I couldnt think of any. The traversals that you do would still result in O(n).
The interviewer did mention he wants my solution to work for millions of nodes. But I didnt think that had much to do with the solution since either way you need to traverse the tree in parts if not whole by loading segments into memory which would still result in O(n).
Anyone has any ideas on this?