Google | Phone Screen | L4 | Reject

A string can be broken into multiple strings and represented as a binary tree where each external node contains a string and a data field and each internal node in the tree contains a numerical value that is the sum of the data fields of its left and right child nodes. For example, if the left child has a data field of 5 and the right child has a data field of 7, the internal node would contain the sum of these values, 12.
Example:

So, here the complete string would be APPLEPIEBANANA

Question: Design a data structure that could represent the above tree.
Created a Node class, and two classes InternalNode node and ExternalNode would inherit from it. Interviewer seemed happy.
Follow up: Find the Nth charater in the string.
Did recursive function, where we can have a count variable, and at any node we can go either go left or right. So we can solve it on O(height of tree).