Complexity Analysis

Worst case scenario time complexity is O(n). Where n is the number of nodes in the tree (in the worst case, we'd need to go through every node to find the value we want).

As this is the recursive solution, it will require memory in the stack for each call of the traversal functions. So on average (balanced binary tree), the space complexity is O(logn). And in the worst case (skewed binary tree), the space complexity will be O(n).

For more information on tree complexities, check out our Big O Notation Cheat Sheet.

Note: Will the space complexity be same if we use an iterative solution for the traversal? Tell us in the discussion!