Log inSign up
easygeeksforgeeksNot Started

Kth Level of a Binary Tree

A curated StudyFlow practice problem with comprehensive editorial and multi-language solutions.

Trees
Solve on geeksforgeeks
Lesson

Problem Statement

Given a binary tree and an integer K, print all nodes at distance K from root (at depth K, where root is at distance 0) from left to right.

Example 1 · Example 1: Depth 2:

Input: root = [1, 2, 3, 4, 5, 8], K = 2 Tree: 1 / \ 2 3 / \ \ 4 5 8
Output: [4, 5, 8]
Explanation: Level 0: 1. Level 1: [2, 3]. Level 2: [4, 5, 8].

Example 2 · Example 2: Root Only (K = 0):

Input: root = [1, 2, 3], K = 0 Tree: 1 / \ 2 3
Output: [1]
Explanation: Distance 0 is root itself.

Constraints:

  • 1 <= N <= 105
  • 0 <= K <= 105
  • 1 <= Node.data <= 105

What You'll Learn

Key principles and algorithmic techniques you will master from this problem:

  • Implement depth-limited search (DLS) on binary trees.
  • Prune search trees when reaching the target depth.
  • Understand why DFS preserves left-to-right ordering across the same level.

Pattern Recognition Trigger

How to instantly recognize this algorithmic pattern when encountering unseen interview questions:

Signals to Look For:

  • Nodes at distance K from root.
  • Kth level elements in left-to-right order.
  • Depth-limited search.

Algorithmic Decision Tree:

  • If node == null return.
  • If k == 0 -> append node.val and return.
  • dfs(node.left, k - 1); dfs(node.right, k - 1).

Connected Patterns:

Binary Tree Level Order TraversalAll Nodes Distance K in Binary TreeBinary Tree Left View

1. Full BFS Level Order Traversal

Intuition

Run standard level-order traversal up to level K. Collect all nodes at level K.

When to apply: Basic baseline check.

Algorithm

  1. Step 1: If root == null return [].
  2. Step 2: Queue q with root.
  3. Step 3: Loop level from 0 to K: if level == K, return all elements in queue.
  4. Step 4: Dequeue level and push children.
C++ SOLUTIONCLEAN & OPTIMIZED
1#include <iostream>
2#include <vector>
3#include <string>
4#include <algorithm>
5using namespace std;
6
7class Solution {
8public:
9 vector<int> Kdistance(TreeNode* root, int k) {
10 if (!root) return {};
11 queue<TreeNode*> q;
12 q.push(root);
13 int curLvl = 0;
14 while (!q.empty()) {
15 int sz = q.size();
16 if (curLvl == k) {
17 vector<int> res;
18 while (!q.empty()) { res.push_back(q.front()->val); q.pop(); }
19 return res;
20 }
21 for (int i = 0; i < sz; ++i) {
22 TreeNode* cur = q.front(); q.pop();
23 if (cur->left) q.push(cur->left);
24 if (cur->right) q.push(cur->right);
25 }
26 curLvl++;
27 }
28 return {};
29 }
30};
31
32int main() {
33 // Sample driver execution
34 cout << "Execution completed successfully." << endl;
35 return 0;
36}
37

Time & Space Complexity

  • Time complexity: O(n) — BFS visits nodes up to level K.
  • Space complexity: O(w) — Queue holds level width w.

2. DFS with Explicit Depth Parameter

Intuition

Call dfs(node, curDepth). If node is null, return. If curDepth == K, add node.val and return (pruning further subtree).

When to apply: DFS tracking absolute depth.

Algorithm

  1. Step 1: Helper dfs(node, curDepth, k, res).
  2. Step 2: If node == null return.
  3. Step 3: If curDepth == k: res.push(node.val); return.
  4. Step 4: dfs(node.left, curDepth + 1, k, res); dfs(node.right, curDepth + 1, k, res).
C++ SOLUTIONCLEAN & OPTIMIZED
1#include <iostream>
2#include <vector>
3#include <string>
4#include <algorithm>
5using namespace std;
6
7class Solution {
8public:
9 void dfs(TreeNode* node, int curDepth, int k, vector<int>& res) {
10 if (!node) return;
11 if (curDepth == k) {
12 res.push_back(node->val);
13 return;
14 }
15 dfs(node->left, curDepth + 1, k, res);
16 dfs(node->right, curDepth + 1, k, res);
17 }
18 vector<int> Kdistance(TreeNode* root, int k) {
19 vector<int> res;
20 dfs(root, 0, k, res);
21 return res;
22 }
23};
24
25int main() {
26 // Sample driver execution
27 cout << "Execution completed successfully." << endl;
28 return 0;
29}
30

Time & Space Complexity

  • Time complexity: O(n) — Prunes search at depth K, visiting at most nodes up to depth K.
  • Space complexity: O(h) — Recursion stack depth up to K <= h.

3. Optimal DFS Countdown with Immediate Pruning

Intuition

Base case: if node is null return. If k == 0: record node.val and return. Otherwise, recurse dfs(node.left, k - 1) and dfs(node.right, k - 1).

When to apply: Optimal gold-standard solution.

Algorithm

  1. Step 1: If node == null return.
  2. Step 2: If k == 0: res.push_back(node.val); return.
  3. Step 3: dfs(node.left, k - 1).
  4. Step 4: dfs(node.right, k - 1).

Depth Pruning DFS Trace for root = [1, 2, 3, 4, 5], K = 2

2 of 2 questions left today
Step 1 / 2
Trace timeline50% explored
Current operationSTEP 1 OF 2
Step 1: Start at root 1 (K=1)
Visual state
Values and pointers at this exact step
tree
Root
1
L
2 (Match)
R
3

Node order shown; add connections to display explicit tree edges.

level 1: 2
Check / comparison
At node 2: K == 0 -> Target level reached!
Decision / next transition
Add 2 to result.
Why this step matters

Step 1: Start at root 1 (K=1). Recurse to left child 2 with K=0.

Step 1 / 2
C++ SOLUTIONCLEAN & OPTIMIZED
1#include <iostream>
2#include <vector>
3#include <string>
4#include <algorithm>
5using namespace std;
6
7class Solution {
8public:
9 void dfs(TreeNode* node, int k, vector<int>& res) {
10 if (!node) return;
11 if (k == 0) {
12 res.push_back(node->val);
13 return;
14 }
15 dfs(node->left, k - 1, res);
16 dfs(node->right, k - 1, res);
17 }
18 vector<int> Kdistance(TreeNode* root, int k) {
19 vector<int> res;
20 dfs(root, k, res);
21 return res;
22 }
23};
24
25int main() {
26 // Sample driver execution
27 cout << "Execution completed successfully." << endl;
28 return 0;
29}
30

Time & Space Complexity

  • Time complexity: O(n) — Never traverses nodes below depth K.
  • Space complexity: O(h) — Call stack strictly bounded by min(h, K).

Approach Comparison Matrix

Side-by-side comparison of time, space, and algorithmic trade-offs across each approach:

ApproachTimeSpaceCore IdeaTrade-off / Bottleneck
1.BFS Level Order QueueO(n)O(w)Queue holds entire level; return level K.Queue memory.
2.DFS with Absolute Depth ParameterO(n)O(h)Tracks depth from 0 upward.None.
3.Optimal DFS CountdownOptimalO(n)O(h)Decrements k until 0; immediately prunes.None. Gold standard.

Common Pitfalls & Crucial Edge Cases

Crucial Edge Cases to Validate:

  • K = 0: returns [root.val].
  • K exceeds tree height: returns empty array [].
  • Skewed tree: returns the single node at depth K.

Interview Tips & Best Practices

How to communicate your thought process and address follow-ups in a live technical interview:

  1. Note that DFS with depth pruning is faster and uses less memory (O(h)) than full BFS queue (O(w)).
  2. Mention that decrementing k on each recursive call avoids passing a current depth and target K separately.

Quick Comprehension Check

Test your intuitive understanding of the core concept in 30 seconds:

1.Why does the DFS approach preserve the required left-to-right ordering across level K?

Back to DSA Sheet