I think the goal of this question was to get you asking for what a degenerate tree is. For all intents and purposes, we can think of degenerate trees as Linked Lists (where each node has exactly one child node). So, simplifying the question to "what is the complexity to search for an integer in a linked list?" the answer would be O(n).