Find All Nodes at K Distance from Root in a Binary Tree

Finding all nodes at k distance from the root of a binary tree is a standard level-traversal problem. Two approaches work: a recursive one that reduces k at each level, and an iterative one that uses BFS to track levels explicitly.

What K Distance from Root Means

In a tree, distance is measured in edges. A node at k distance from the root is reachable by following exactly k edges downward from the root. The root itself is at distance 0.

Consider this example tree:

        15
       /  \
      12   18
     / \     \
    8  13    24
             / \
            22  27

• Nodes at distance 0: 15 (the root)
• Nodes at distance 1: 12, 18
• Nodes at distance 2: 8, 13, 24
• Nodes at distance 3: 22, 27

“Distance from root” and “level” are interchangeable here: distance k equals level k. Level 0 is the root; level 1 is the root’s children; level 2 is the grandchildren; and so on. The problem is essentially “print level k of the tree.”

Recursive Approach

The recursive logic is compact. If the current node is at distance 0 from its caller’s perspective, it is at the target distance from the root, so print it. Otherwise, recurse on each child with k reduced by 1.

Algorithm

• If the node is NULL, return.
• If k == 0, print the node’s data and return.
• Recursively call the function on the left child with k - 1.
• Recursively call the function on the right child with k - 1.

C Implementation

#include <stdio.h>
#include <stdlib.h>

struct Node {
    int data;
    struct Node *left, *right;
};

struct Node* newNode(int data) {
    struct Node* node = (struct Node*)malloc(sizeof(struct Node));
    node->data  = data;
    node->left  = node->right = NULL;
    return node;
}

/* Print all nodes at distance k from root */
void printAtK(struct Node* root, int k) {
    if (root == NULL) return;
    if (k == 0) {
        printf("%d ", root->data);
        return;
    }
    printAtK(root->left,  k - 1);
    printAtK(root->right, k - 1);
}

int main() {
    struct Node* root        = newNode(15);
    root->left               = newNode(12);
    root->right              = newNode(18);
    root->left->left         = newNode(8);
    root->left->right        = newNode(13);
    root->right->right       = newNode(24);
    root->right->right->left  = newNode(22);
    root->right->right->right = newNode(27);

    printf("Nodes at distance 3: ");
    printAtK(root, 3);   /* Output: 22 27 */
    return 0;
}

To see how the k reduction works, trace the call tree for k = 2 against the example:

• printAtK(15, 2) calls printAtK(12, 1) and printAtK(18, 1).
• printAtK(12, 1) calls printAtK(8, 0) and printAtK(13, 0), which print 8 and 13.
• printAtK(18, 1) calls printAtK(NULL, 0) (left of 18 is absent, no output) and printAtK(24, 0), which prints 24.
• Final output: 8, 13, 24.

Each level of the tree peels off one unit of k. The function reaches k = 0 precisely at the target depth.

Iterative Approach Using BFS

The iterative version processes the tree one level at a time. A queue holds all nodes at the current level. A counter tracks which level the queue currently represents. When the counter matches k, print all nodes in the queue.

This is breadth-first search with a level counter. The discipline that makes it work: before advancing the counter, dequeue every node on the current level and enqueue their children. That way the queue always holds exactly one level at a time.

Algorithm

• Enqueue the root. Set level = 0.
• While the queue is not empty:
  • Note how many nodes are currently in the queue (this is the full current level).
  • If level == k, print all nodes in the queue and stop.
  • For each node in the current level: dequeue it and enqueue its non-null children.
  • Increment level.

C Implementation

#include <stdio.h>
#include <stdlib.h>

#define MAXQ 1024

struct Node {
    int data;
    struct Node *left, *right;
};

struct Node* newNode(int data) {
    struct Node* node = (struct Node*)malloc(sizeof(struct Node));
    node->data  = data;
    node->left  = node->right = NULL;
    return node;
}

void printAtKIterative(struct Node* root, int k) {
    if (root == NULL) return;

    struct Node* queue[MAXQ];
    int front = 0, rear = 0;
    queue[rear++] = root;
    int level = 0;

    while (front < rear) {
        int levelSize = rear - front;   /* nodes at the current level */
        if (level == k) {
            for (int i = front; i < rear; i++)
                printf("%d ", queue[i]->data);
            return;
        }
        for (int i = 0; i < levelSize; i++) {
            struct Node* curr = queue[front++];
            if (curr->left)  queue[rear++] = curr->left;
            if (curr->right) queue[rear++] = curr->right;
        }
        level++;
    }
}

int main() {
    struct Node* root        = newNode(15);
    root->left               = newNode(12);
    root->right              = newNode(18);
    root->left->left         = newNode(8);
    root->left->right        = newNode(13);
    root->right->right       = newNode(24);
    root->right->right->left  = newNode(22);
    root->right->right->right = newNode(27);

    printf("Nodes at distance 3: ");
    printAtKIterative(root, 3);   /* Output: 22 27 */
    return 0;
}

The queue holds at most one full level at a time, reaching its peak size at the widest level of the tree.

One output-order note: the BFS version prints nodes left to right across the level. The recursive version visits them in DFS order (left subtree before right), which happens to match left-to-right for standard binary trees but can differ in non-standard structures. If the problem requires level-order output specifically, use BFS.

Time and Space Complexity

Both approaches visit every node exactly once in the worst case.

Approach	Time complexity	Auxiliary space
Recursive	O(n)	O(h) — call stack depth equals tree height
Iterative BFS	O(n)	O(w) — queue holds the widest level, worst case O(n)

Where h is the height and w is the maximum width:

• Balanced binary tree: h = O(log n), w = O(n) at the bottom level.
• Skewed tree (every node has exactly one child): h = O(n), w = O(1).

For a skewed tree the recursive approach uses O(n) stack space, which can exceed the system’s recursion limit on large inputs. BFS uses O(1) queue space for the same tree. The opposite holds for a wide, shallow tree: BFS queue grows to O(n) while the recursive stack stays shallow.

The space complexity of algorithms article derives the O(log n) recursion stack result for binary search in detail. The derivation for this problem is identical: each recursive call halves the remaining depth (in a balanced tree), so at most log n frames are active simultaneously.

Choosing between the two approaches:

• For trees with balanced or near-balanced structure and modest depth, either approach is correct.
• For very deep or skewed trees where recursion depth is a concern, use BFS.
• If the problem output must be in level order (left to right within a level), use BFS. The recursive approach cannot guarantee this without extra bookkeeping.

Variations You Will See in Placement Tests

Placement coding rounds vary this problem in predictable ways. The base form (print nodes at distance k) is the entry point.

Count Instead of Print

Return an integer count instead of printing. The change is minimal:

• Base case: when k == 0, return 1 (instead of printing).
• Recursive return: return printAtK(root->left, k-1) + printAtK(root->right, k-1).

Return a List

Return a list or vector instead of printing. Replace the print statement with a list append. The algorithm is otherwise unchanged.

K Distance from a Specific Node (Not the Root)

This is a harder variant. Nodes can be above or below the target node at distance k. Solving it requires two passes: one to find the target node, then logic to handle both downward (subtree) and upward (ancestor-path) directions. The program to find all symmetric pairs in an array covers a related two-direction scanning pattern over a linear structure. The tree version extends that logic to a hierarchical one.

Count Nodes at Every Level

Instead of targeting a single k, print the count of nodes at every level from 0 to the tree height. Use BFS and record the queue size before each level expansion. This is a small generalisation of the iterative version above.

For warmup on two-direction reference-point problems (relevant for the k-from-specific-node variant), see the equilibrium index of an array problem: it shares the structure of “consider both left and right from a reference point and combine the results.”

Where This Problem Fits in the Placement Syllabus

Binary tree traversal is a standard topic in placement coding rounds at Indian IT companies. TCS NQT, Infosys Hackwithinfy, AMCAT Automata, and Cognizant GenC assessments all include tree problems in their higher-difficulty coding sections.

The k-distance problem tests three specific things interviewers track:

• Whether you can implement a clean recursive base case without off-by-one errors in k. Getting this wrong is the most common mistake.
• Whether you understand that DFS (recursive) and BFS (iterative) produce different output orderings for the same set of nodes.
• Whether you reach for the iterative version when the problem explicitly requires level-order output or when the input tree is known to be deeply skewed.

One note on output interpretation: the recursive C code above prints nodes in the order DFS visits them. BFS prints them strictly left to right across the level. Both produce the same set; they differ only in sequence. Most automated judges accept either order unless the problem statement specifies otherwise.

The recursive vs. iterative decision here, explicit queue vs. implicit call stack, maps directly to a trade-off in LLM application design. TinkerLLM at ₹299 is where that connection stops being abstract: you build an LLM-backed project and decide how much conversation history to hold in memory, which is the O(n) queue space problem applied to a different kind of tree.