The answer
Traversing an entire tree to visit every node is O(N) because you must process all N nodes. Searching a perfectly balanced Binary Search Tree is O(log N).
Analyzing the Time Complexity of Recursive Functions
Is recursive traversal of a Tree O(N) or O(log N)?
More FAQs in Analyzing the Time Complexity of Recursive Functions
You determine the total number of times the function is recursively called (the nodes in the recursion tree) and multiply it by the amount of non-recursive work done in each call.
If it decrements by 1 (e.g., n-1) and makes a single call, it forms a straight line of N calls, resulting in O(N) Linear Time.
Because instead of decrementing by 1, it divides the input size by 2 on each recursive call, slashing the required number of calls logarithmically.
Still have questions?
Browse all our FAQs or reach out to our support team
Want to upskill yourself?
Your learning library
Small steps. Big possibilities.
Find your next course. Build something great.