Katkat
Back

Find All Tree Nodes at Distance K

AppleSoftware Engineer · Onsite
MediumSoftware EngineerOnsiteCoding & Algorithms

Last updated

This problem tests tree traversal, graph representation (converting a tree to an undirected graph), and breadth-first search (BFS) to find nodes at a specific distance.

Problem Statement

Given the root of a binary tree, a target node reference, and an integer k, return a list of values of all nodes in the tree that are exactly k distance away from the target node. You should return the result as a list of integers sorted in ascending order.

Constraints

  • The tree contains between 1 and 500 nodes.
  • Each node's value is between 0 and 500.
  • k is between 0 and 1000.
  • The target node is guaranteed to exist in the tree.

Function Signature

class TreeNode:
    def __init__(self, val=0, left=None, right=None):
        self.val = val
        self.left = left
        self.right = right

def distanceK(root: TreeNode, target: TreeNode, k: int) -> list[int]:

Examples

Example 1:

  • Input: root = [3,5,1,6,2,0,8,null,null,7,4], target = 5, k = 2
  • Output: [1, 4, 7]
  • Explanation: The nodes at distance 2 from the node with value 5 are [1, 4, 7].

Example 2:

  • Input: root = [1], target = 1, k = 0
  • Output: [1]

Edge Cases

  • k = 0: The output should be just the target node value.
  • k is greater than the tree height: Return an empty list.
  • Tree with only one node.

Implement the solution efficiently, ensuring you handle the undirected nature of the distance (i.e., you can move up to parent nodes).

Hints

Hint 1

Since binary tree nodes typically only store children, consider first building a parent mapping or converting the tree into an adjacency list representation of a graph.

Hint 2

Once you have an undirected graph structure, the problem simplifies to finding all nodes at distance `k` from the target node using Breadth-First Search (BFS).

Hint 3

Keep track of visited nodes during your BFS traversal to prevent moving backward or cycles if the tree structure were to change.

Follow-up questions

  • How would your approach change if the tree was a generic N-ary tree rather than a binary tree?
  • What is the time and space complexity of your solution, and can you optimize the space if you avoid explicit graph construction?
  • How would you handle finding nodes at distance k if the graph contained cycles?