#863

Medium

auto_awesomeBinary-tree traversal and state tracking

LeetCode Problem Workspace

All Nodes Distance K in Binary Tree

Find all nodes at distance K from a target node in a binary tree using various tree traversal techniques.

hash table tree depth first search breadth first search binary tree

Problem Statement

Given a binary tree root, a target node, and an integer K, return the values of all nodes that are exactly K distance away from the target. The tree consists of nodes with unique values, and the target node is guaranteed to exist within the tree.

You must account for all paths that lead to nodes at distance K, including moving both upward and downward from the target node. The order of nodes in the output does not matter, but you must ensure correct distance tracking and edge cases like trees with very few nodes or large values for K.

Examples

Example 1

Input: root = [3,5,1,6,2,0,8,null,null,7,4], target = 5, k = 2

Output: [7,4,1]

The nodes that are a distance 2 from the target node (with value 5) have values 7, 4, and 1.

Example 2

Input: root = [1], target = 1, k = 3

Output: []

Example details omitted.

Constraints

The number of nodes in the tree is in the range [1, 500].
0 <= Node.val <= 500
All the values Node.val are unique.
target is the value of one of the nodes in the tree.
0 <= k <= 1000

Solution Approach

DFS with Backtracking

DFS can be employed to traverse the tree, where you backtrack after reaching the target node. During the traversal, maintain a map of node values and distances, ensuring you account for both the upward and downward distance from the target. This method ensures that once the target is found, the distances to the other nodes are tracked correctly.

BFS from Target Node

Starting from the target node, a BFS traversal can explore all nodes at increasing distances. By maintaining a queue and a visited set, you can efficiently compute nodes that are exactly K distance away. This method works well for level-order traversal and guarantees you explore all nearby nodes before moving further away.

Use of Hash Map for Distance Tracking

A hash map can be used to store distances from the target node during either DFS or BFS. This allows you to keep track of the exact distance from the target to each node. The key advantage here is that you avoid redundant calculations, optimizing the search for nodes at the desired distance.

Complexity Analysis

Metric	Value
Time	Depends on the final approach
Space	Depends on the final approach

Both the time and space complexities depend on the approach chosen. For DFS, time complexity is O(N), where N is the number of nodes in the tree, since each node is visited once. The space complexity is O(H) for the recursion stack, where H is the height of the tree. For BFS, time complexity is O(N) and space complexity is O(N), as the entire tree could potentially be stored in a queue at once.

What Interviewers Usually Probe

Candidates should demonstrate familiarity with tree traversal methods such as DFS and BFS.
Be aware of the candidate's ability to handle edge cases, especially small trees or large K values.
Look for candidates who suggest methods for efficiently tracking distances, using a hash map or other techniques.

Common Pitfalls or Variants

Common pitfalls

Forgetting to account for both upward and downward traversals when calculating distances from the target.
Not handling cases where K is larger than the height of the tree, which results in empty output.
Misusing the BFS or DFS traversal, leading to inefficient or incorrect traversal of the tree.

Follow-up variants

Modify the problem to find all nodes within a range [L, R] of distances from the target node.
Implement the solution using an iterative DFS approach instead of recursive DFS.
Extend the problem to handle binary search trees (BST) where additional properties can be used for optimization.

FAQ

How do I solve the All Nodes Distance K in Binary Tree problem?

You can solve this by using Depth-First Search (DFS) or Breadth-First Search (BFS) with a hash map to track distances from the target node.

What is the time complexity of the solution?

The time complexity is O(N) for both DFS and BFS, where N is the number of nodes in the tree.

Can the tree contain only one node?

Yes, the tree can contain a single node, in which case the solution will depend on the value of K.

How do I handle a case where K is larger than the tree height?

In such cases, the result will be an empty array since no nodes exist at a distance larger than the height of the tree.

How do I optimize space usage when solving this problem?

To optimize space, consider iterative methods like BFS with a queue and avoid using large recursion stacks in DFS.

terminal

Solution

Solution 1: DFS + Hash Table

We first use DFS to traverse the entire tree and save each node's parent node in the hash table $\textit{g}$.

1

2

3

4

5

6

7

8

9

10

11

12

13

14

15

16

17

18

19

20

21

22

23

24

25

26

27

28

29

30

31

32

# Definition for a binary tree node.
# class TreeNode:
#     def __init__(self, x):
#         self.val = x
#         self.left = None
#         self.right = None


class Solution:
    def distanceK(self, root: TreeNode, target: TreeNode, k: int) -> List[int]:
        def dfs(root, fa):
            if root is None:
                return
            g[root] = fa
            dfs(root.left, root)
            dfs(root.right, root)

        def dfs2(root, fa, k):
            if root is None:
                return
            if k == 0:
                ans.append(root.val)
                return
            for nxt in (root.left, root.right, g[root]):
                if nxt != fa:
                    dfs2(nxt, root, k - 1)

        g = {}
        dfs(root, None)
        ans = []
        dfs2(target, None, k)
        return ans

Continue Practicing

#865 smallest subtree with all the deepest nodes #987 vertical order traversal of a binary tree #653 two sum iv input is a bst