Is recursive traversal of a Tree O(N) or O(log N)?
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).
Verify This Answer
Cross-check this information using these trusted sources:
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