Trees and BST Recursion Drill round·Engineering·Hard·20 min

TCS Prime Software Engineer — Trees and BST Recursion Drill

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
Prime Software Engineer
Duration
20 min
Difficulty
Hard
Completions
New
Updated
2026-06-09

What this round is about

  • Topic focus. Two whiteboard problems, a binary-tree traversal and a binary search tree validation, both solved with recursion and then defended on complexity.
  • Conversation dynamic. The panelist puts a problem on a card, lets you drive, and pushes on your base case, your return value, and your memory use rather than reading the statement to you.
  • What gets tested. Whether you can state the base case, say what each recursive call returns, trace the tree by hand, and give an iterative alternative using a queue or a stack on demand.
  • Round format. A live spoken session with a shared whiteboard where you draw the tree, number the visiting order, and dry-run your own code.

What strong answers look like

  • Recursion stated first. You name the base case and what the call hands back to its parent before writing code, for example the height call returns the larger child height plus one.
  • Complexity with the stack. You quote O of n time and then volunteer O of h space for the recursion stack without being asked.
  • BST range insight. You validate a BST by carrying a valid range down the recursion, and you note that an inorder traversal of a valid BST is strictly increasing.
  • Iterative on demand. When asked, you reach cleanly for a queue for level order or an explicit stack for inorder instead of freezing.

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

  • Local-only BST check. Comparing each node with just its immediate children accepts invalid trees, carry a min and max range down instead.
  • Forgetting the stack. Saying O of n time but ignoring the O of h recursion memory, always account for the call stack.
  • Silent coding. Writing in silence so the panel cannot follow you, narrate each step and each pop from the queue or stack.
  • No base case. Jumping into the recursive step without the terminating case, state what stops the recursion before the rest.

Pre-interview checklist (2 minutes before you start)

  • Recall the traversal templates. Have level order with a queue and inorder with a stack ready to write from memory.
  • Have a sample tree. Be ready to draw a four to seven node tree to trace on the board.
  • Identify the base case habit. Practise saying the terminating case first for any tree function.
  • Think of the BST range trick. Rehearse validating a BST by passing a lower and upper bound down.
  • Re-read the skewed-tree effect. Be ready to explain how O of h becomes O of n on a chain.
  • Pull up complexity phrasing. Have the words for time and recursion-stack space ready for every solution.

How the AI behaves

  • Probes every claim. If you say O of n it asks about memory, if you validate locally it hands you a tree that defeats the check.
  • No mid-interview praise. It acknowledges the specific thing you said and pushes deeper, it will not say great answer.
  • Interrupts on hand-waving. It stops you when complexity is vague or when you refuse to draw and asks you to be concrete.
  • One question at a time. It asks a single thing, waits, and follows up before moving to the next problem.

Common traps in this type of round

  • Range-free validation. Checking only node against immediate children and missing a deep ordering violation.
  • Stack-cost omission. Quoting time complexity while ignoring the recursion stack of O of h.
  • Iterative freeze. Going blank when asked to remove recursion instead of reaching for a queue or a stack.
  • Two-children deletion slip. Mishandling the inorder-successor replacement when deleting a BST node with two children.
  • Reciting without tracing. Stating a traversal name but being unable to number the visiting order on the drawn tree.
  • Skipping clarification. Coding before asking whether the tree is empty, balanced, or has unique values.

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. 1Level-Order Traversal of a Binary Tree

    Given the root of a binary tree, return its node values level by level, from the root level down to the deepest level, with each level as its own group from left to right. Then explain your recursion base case, give the time and space complexity including the recursion stack, and be ready to produce an iterative version on request.

    Example inputTree: 1\n / \\\n 2 3\n / \\ \\\n 4 5 6
    Example output[[1], [2, 3], [4, 5, 6]]
    • The tree may be empty (root is null); return an empty list in that case.
    • Node values fit in a 32-bit integer; the tree has at most 10^4 nodes.
    • State both the recursive and the iterative (queue-based BFS) approach and their complexity.
    • Draw the tree on the whiteboard and number the nodes in the order they are visited.
  2. 2Validate a Binary Search Tree

    Given the root of a binary tree, determine whether it is a valid binary search tree, where every node's value is greater than all values in its left subtree and less than all values in its right subtree. A check that only compares each node with its immediate children is not sufficient. Explain what each recursive call returns and the complexity including the recursion-stack space.

    Example inputTree: 10\n / \\\n 5 15\n / \\\n 6 20
    Example outputfalse (node 6 is in the right subtree of 10 but is less than 10, so the BST property is violated)
    • Values may be treated as unique; decide and state how you would handle duplicates.
    • An empty tree and a single node are both valid BSTs.
    • Carry a valid min-max range down the recursion, or use the fact that an inorder traversal of a valid BST is strictly increasing.
    • On the whiteboard, draw a tree that passes a naive parent-child check but is not a valid BST, and trace your code on it.

Interview framework

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

Recursion Formulation
How clearly you state the base case and what each recursive call returns before coding, rather than guessing at the recursive step.
25%
Complexity And Stack Reasoning
Whether you give both time and recursion-stack space, and can defend the figures by tracing the actual work done.
20%
Bst Property Insight
Whether you exploit the ordering property with a propagated range and turn an O of n scan into an O of h descent.
20%
Iterative Alternative Fluency
Whether you can drop recursion and drive a queue or stack by hand when the panelist asks for it.
15%
Whiteboard Tracing
How accurately you number the visiting order on the drawn tree and dry-run your own code across it.
12%
Approach Communication
Whether you narrate each step and the contents of the queue or stack so the panel can follow you, instead of coding in silence.
8%

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 and Return Formulation20%
  • BST Range Validation Insight20%
  • Time and Recursion-Stack Complexity18%
  • Iterative Traversal Conversion15%
  • Whiteboard Trace Fidelity15%
  • Input Clarification and Edge Handling12%

Common questions

What does the TCS Prime trees and BST coding round actually test?
It tests whether you reason about a tree problem as a recursion problem. The panelist puts two problems on cards, a binary-tree traversal and a binary search tree question, and listens for three things: the base case that stops the recursion, what each recursive call returns to its parent, and the time and space complexity including the recursion-stack cost of O of h. You also draw the tree on a whiteboard and trace the visiting order by hand. When asked, you give an iterative alternative using a queue for level order or a stack for inorder.
How should I structure my answer before I start coding?
Clarify the input first, then state your approach in plain words before writing anything. Name the base case out loud, say what the recursive call returns, and describe how you combine the left and right subtree results. Then sketch the tree and trace it. The panelist does not read the full statement like an online judge, so you must ask about constraints yourself. Coding in silence is penalised, so narrate each step. Finish by stating time and space complexity, and remember to count the recursion stack.
What are the most common mistakes in this round?
The classic one is validating a binary search tree by only comparing each node with its immediate left and right child, which wrongly accepts trees that violate the ordering deeper down. You must carry a valid range down the recursion instead. Other frequent errors: quoting time complexity but forgetting the recursion stack costs O of h space, freezing when asked for an iterative version, mishandling the two-children case in BST deletion, and going silent so the panel cannot follow your approach or offer a hint.
How is this AI interviewer different from a real TCS panel?
It behaves like a real panelist, not a chatbot. It stays in character as Aarav, a senior engineer, never breaks to explain itself, and never tells you whether you passed. It probes every claim: if you say O of n, it asks about memory; if you validate a BST with a local check, it hands you a tree that defeats it. It asks one question at a time and always follows up at least once. The difference is consistency, it gives every candidate the same depth of probing and a transcript-backed scorecard afterward.
How is the round scored?
Scoring is built from observable behaviour in the transcript and the whiteboard, not delivery style. Dimensions include how clearly you formulate the recursion, whether your complexity analysis is correct including the stack, whether you exploit the BST ordering property to get an O of h descent, whether you can produce an iterative alternative, and how well you trace the tree on the board. Each dimension has a threshold for adequate versus strong, and the report quotes the exact moment a complexity claim or BST insight could not be justified.
What should I do in the first two minutes?
Read the first card aloud and restate the problem in your own words. Ask one or two clarifying questions about the input, for example whether the tree is balanced, whether values are unique, and what should happen on an empty tree. Pull up the whiteboard early and draw a small example tree, four to seven nodes, because you will trace on it. State the base case before you write code. Do not start typing a solution before you have said what each recursive call returns.
How do I handle the follow-up when the tree is skewed?
A skewed tree is a chain, so its height h equals the number of nodes n. Explain that operations you described as O of h, like search, insert, or the recursion depth of a traversal, degrade to O of n, and the recursion stack grows to O of n as well, risking a stack overflow on very deep trees. If asked to avoid that, reach for the iterative version: a queue for level order, or an explicit stack for inorder, which gives you control over memory and removes the call-stack limit.
What does a strong answer sound like on the BST validation problem?
A strong answer says: I will carry a valid range down the recursion. For the left child the upper bound becomes the current node value, for the right child the lower bound becomes the current node value, and any node outside its range means it is not a valid BST. The candidate notes that an inorder traversal of a valid BST is strictly increasing, offers that as an alternative check, and states O of n time and O of h space for the recursion stack. When handed a tree that passes a naive local check but is not a valid BST, they trace their range-based code and show it correctly rejects it.
Why does the interviewer keep asking what each recursive call returns?
Because that single question separates candidates who understand recursion from candidates who memorised a solution. A tree algorithm is defined by what each call hands back to its parent: a height returns the larger of the two child heights plus one, a diameter call returns a height while updating a running maximum, a validate call returns a boolean for its whole subtree. If you can state the return value precisely, you can build any tree algorithm. If you cannot, your code is a guess, and the panelist will keep probing until you can articulate it.
Do I need to write perfect compiling code, or is the approach enough?
Approach and reasoning carry the most weight, but you should write code clean enough to dry-run by hand. The panelist will ask you to trace your own code on the tree you drew, node by node, so off-by-one errors and a missing base case will surface. Pseudocode with a correct base case, a clear recursive step, and a correct combine is stronger than syntactically perfect code you cannot explain. State your language, keep variable names readable, and be ready to walk the queue or the stack contents at each step.
What level of difficulty should I expect at the Prime tier specifically?
Prime is the highest TCS hiring band, above Ninja and Digital, and the question difficulty rises accordingly. Expect medium-hard tree problems: level order by levels, height and diameter in one pass, lowest common ancestor, validate a BST, kth smallest, or inorder successor. The basic questions overlap with lower tiers, but the panel pushes further on complexity, on the iterative alternative, and on edge cases like skewed or empty trees. The bar rewards a correct base case, tight complexity including the stack, and the BST-property insight that turns an O of n scan into an O of h descent.

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.