Recursion Tree and Binary Search Trace round·Engineering·Medium·20 min

TCS Ninja Coding Interview — Recursion Tree and Binary Search Trace

20 min · 1 credit · scorecard at the end
Z
ZeroPitch Research Desk
Updated 2026-06-09 · Newly added · be among the first to take it
Field
Engineering
Company
Tata Consultancy Services
Role
Assistant System Engineer Trainee (Ninja)
Duration
20 min
Difficulty
Medium
Completions
New
Updated
2026-06-09

What this round is about

  • Topic focus. Two whiteboard problems, one on binary search for the first and last occurrence in a sorted array with duplicates, and one on recursion with factorial and Fibonacci.
  • Conversation dynamic. A TCS panellist makes you talk while you code, state the base case before the recursive call, and trace the algorithm on a concrete input rather than narrating in the air.
  • What gets tested. Whether you can write correct foundational code, draw the recursion tree, move the binary search pointers, and give both time and recursion-stack space complexity.
  • Round format. A twenty-minute live coding round with a shared whiteboard, problems shown on cards, conducted at the foundational searching, sorting, and recursion altitude.

What strong answers look like

  • Base case first. You say factorial of zero or one returns one before you write the recursive call, and you point at that base case on the board.
  • Grounded logarithmic reasoning. You move left, right, and mid on a real array and explain that the search space halves each step, so it is order log n, instead of just reciting the number.
  • Recursion tree drawn. For Fibonacci you draw the tree for n equals five, point at the repeated subtrees, and explain why recomputing them makes it exponential.
  • Complexity stated unprompted. You finish each problem by stating time complexity and recursion-stack space, including order n stack depth for the recursive version.

What weak answers look like (and how to avoid them)

  • Recursive call before base case. Writing the self-call with no stated stopping condition. Say the base case out loud first, every time.
  • Untraced code. Writing the function and never running it on a sample input, so off-by-one and pivot errors hide. Dry-run a small input on the board before you claim it works.
  • Silent on complexity. Going quiet when asked the time or space cost. Always volunteer both, and include the call-stack space for recursion.
  • Recited log n. Saying order log n with no reason. Tie it to the search space halving at each midpoint.

Pre-interview checklist (2 minutes before you start)

  • Recall the factorial base case. Have factorial of zero or one returns one ready to say before any recursive code.
  • Have a binary search template in mind. Know your left, right, and mid update and which way you move when the value equals the target for first versus last occurrence.
  • Think of the Fibonacci tree. Be ready to draw fib of five branching into fib of four and fib of three and point at the repeats.
  • Identify your complexity lines. Be ready to state time and recursion-stack space for both the recursive and the iterative version.
  • Pull up the whiteboard early. Plan to put pointers and boxes on the page in the first couple of turns rather than narrating in the air.
  • Re-read the array. Confirm whether the input is sorted and whether it has duplicates before you choose your approach.

How the AI behaves

  • Probes every answer. It asks at least one follow-up on each problem, pushing for the base case, the trace, or the complexity you left out.
  • No mid-round praise. It will not say great answer or validate you, it acknowledges the specific thing you said and then pushes deeper.
  • Redirects to the board. If you narrate without drawing, it tells you to pull up the whiteboard and trace it within the first couple of turns.
  • Pressure-tests memorised answers. If you recite a complexity, it makes you prove why on the board rather than accepting the number.

Common traps in this type of round

  • Missing base case. Starting the recursion with no stated stopping condition, then being unable to explain the stack overflow.
  • Diagram-verbal mismatch. Saying you move right when the board shows the pointer going left, or a tree that does not match your spoken walkthrough.
  • Proxy complexity. Claiming order log n or order n without grounding it in the halving or the stack depth.
  • Naive Fibonacci with no insight. Writing the exponential version and not recognising the overlapping subproblems that cause it.
  • Iterative versus recursive dodge. Refusing to pick one and say why you would use it in real code.
  • Going silent under nerves. Solving in your head with no narration, leaving nothing for the interviewer to follow or verify.

Sample problems you'll face

The 2 problems below are the same ones you'll work through in the live session — no surprises. Read the constraints carefully; the AI persona will refer you to the on-canvas card by problem number.

  1. 1First and Last Occurrence in a Sorted Array

    Given a sorted array of integers that may contain duplicate values, and a target value, find the index of the first occurrence and the index of the last occurrence of the target. If the target is not present, return -1 for both. Use binary search so the solution runs in logarithmic time, and be ready to trace the left, right, and mid pointers on a sample array.

    Example inputarr = [1, 1, 2, 2, 2, 3, 4], target = 2
    Example outputfirst = 2, last = 4
    • The array is sorted in non-decreasing order and may contain duplicates.
    • Target time complexity is O(log n); a linear scan is not accepted.
    • State which direction you move the pointers when arr[mid] equals the target, separately for the first and the last occurrence.
    • On the whiteboard, draw the array and mark left, right, and mid at each step, showing how the search space halves until the first and last positions are found.
  2. 2Factorial and Fibonacci with the Recursion Tree

    Write a recursive function for factorial of n. Then write a recursive function for the nth Fibonacci number. State the base case before you write the recursive call in each. For Fibonacci, draw the recursion tree for n = 5, mark the base cases, and explain why the naive recursive version recomputes work. Give the time complexity and the recursion-stack space for each function, and say what causes a stack overflow.

    Example inputfactorial: n = 4 fibonacci: n = 5
    Example outputfactorial(4) = 24 fibonacci(5) = 5
    • State the base case explicitly before writing any recursive call: factorial of 0 or 1 returns 1; fib(0) = 0 and fib(1) = 1.
    • Give time complexity and recursion-stack space separately; note the recursive call stack uses O(n) auxiliary space.
    • Explain what causes a stack overflow if the base case is never reached.
    • Draw the recursion tree for n = 5 on the whiteboard, mark the base case, and circle at least one repeated subproblem such as fib(2).

Interview framework

You will be scored on these 5 dimensions. The full rubric with definitions is below.

Base Case Discipline
Whether you state the recursion stopping condition before the self-call and point to it on the board, rather than discovering it after being asked.
22%
Binary Search Trace Accuracy
How correctly you move left, right, and mid on a real array and show the first-versus-last direction, not just describe binary search in words.
20%
Complexity Articulation
Whether you state both time and recursion-stack space and ground them in the halving or the stack depth instead of reciting Big O numbers.
20%
Recursion Tree Reasoning
How well you draw the Fibonacci tree, spot the repeated subproblems, and connect them to the exponential cost and the crash condition.
18%
Out Loud Problem Narration
How much you talk through your logic and dry-run while you solve, the way you would explain code to a lead at TCS, versus solving silently.
20%

What we evaluate

Your final scorecard breaks down across these dimensions. The full rubric and tier criteria are revealed inside the interview itself.

  • Recursion Base Case Discipline20%
  • Binary Search Trace Correctness18%
  • Complexity Articulation and Grounding18%
  • Recursion Tree and Subproblem Insight16%
  • Iterative versus Recursive Judgment14%
  • Out Loud Reasoning Narration14%

Common questions

What does the TCS Ninja coding round actually test?
It tests whether you can write correct foundational code and explain it out loud. The interviewer gives you two problems, one on searching like binary search for the first and last occurrence in a sorted array, and one on recursion like factorial and Fibonacci. You are expected to state the base case before writing the recursive call, draw the recursion tree on the whiteboard, trace the binary search midpoint movement on a sample input, and give both the time complexity and the recursion-stack space. It is a fundamentals-and-communication bar, not a competitive-programming bar.
How should I structure my answer in a coding round like this?
Talk before you write. For a recursion problem, say the base case first, then the recursive relation, then write the code, then dry-run it on a small input out loud. For binary search, state your left, right, and mid, then walk the pointers on a concrete array on the whiteboard. Finish every problem by stating the time complexity and the space complexity, including the recursion-stack space. Narrating while you solve is half the score, because at TCS you explain your code to a lead every day.
What are the most common mistakes candidates make here?
The three big ones are writing the recursive call before stating the base case, writing code and never dry-running it on a sample input so off-by-one and pivot errors slip through, and going silent when asked for complexity. Many candidates also recite that binary search is order log n without being able to say why the search space halves. Another frequent miss is writing naive recursive Fibonacci and being unable to explain why recomputing the same subproblems makes it exponential.
How is this AI interviewer different from a real TCS interviewer?
It behaves like a real TCS campus panellist and stays in character the whole time. It probes every answer at least once, never praises you mid-round, and pushes you to the whiteboard quickly instead of letting you narrate in the air. The difference is that it is available on demand, it is consistent across every attempt, and it produces a transcript-backed scorecard afterward that names the exact moment your trace or your base case broke, which a real interviewer rarely gives you.
How is the scoring done in this round?
You are scored on observable behaviours from the transcript and the whiteboard, not on delivery or accent. The dimensions include how clearly you state and use the base case, how correctly you trace binary search and state why it is logarithmic, how accurately you give time and recursion-stack space complexity, how well you compare iterative versus recursive, and how much you narrate your logic while solving. The post-session report breaks each of these down and quotes specific moments from your answers.
What should I do in the first two minutes of the round?
Settle your nerves and listen to the first problem carefully before touching the keyboard or the board. Restate the problem in one line so you both agree on it, including whether the array can have duplicates. Then say your plan out loud in plain words before you write anything. Pull up the whiteboard early, because the interviewer will make you trace binary search and draw the recursion tree there anyway, so get boxes and pointers on the page in the first couple of turns.
How do I handle it when the interviewer asks what causes a stack overflow?
Tie it to the base case and the call stack directly. Say that every recursive call adds a new frame to the call stack, and if the base case is never reached or is wrong, the recursion never stops and the stack runs out of memory, which is the stack overflow. Then connect it back to your own code by pointing at your base case on the whiteboard and showing that it is reached for the inputs you were given. Avoid vague answers like too much recursion.
What does a strong answer sound like in a TCS recursion question?
A strong answer states the base case first, for example factorial of zero or one returns one, then gives the recursive step, then dry-runs a small input like factorial of four down to the base case out loud. For Fibonacci it draws the recursion tree for n equals five, points at the repeated subtrees, and explains the exponential time and the order n stack depth. It ends by saying which of iterative or recursive the candidate would use in real code and why, without being asked twice.
Why does the interviewer keep pushing me to the whiteboard?
Because this round grades your trace and your recursion tree as a first-class signal, not just your final answer. A real TCS panellist wants to see the midpoint pointers move on a concrete array and the recursion tree drawn with the base case marked, because that is how they know you actually understand the algorithm rather than having memorised a template. If you only narrate in the air, there is nothing to verify, so the interviewer redirects you to draw within the first couple of turns.
Do I need competitive programming skills to pass the TCS Ninja round?
No. The Ninja band is a high-volume entry hire and the coding bar is set to foundational data structures and algorithms, because the pool spans both CS and non-CS branches. You need to be fluent in searching, sorting, and recursion, able to write basic programs like factorial, Fibonacci, palindrome, and string reversal, and able to explain complexity. Advanced topics and contest tricks are not what this round tests. Fluency and clear explanation of the basics beat half-remembered advanced algorithms.

Sources this interview is built on

Real candidate-report URLs (Glassdoor / AmbitionBox / PrepInsta / GeeksforGeeks / Medium) reviewed when authoring the questions, persona, and rubric. Verify the realism yourself.