We use cookies (including Google cookies) to personalize ads and analyze traffic. By continuing to use our site, you accept our Privacy Policy.

SimplyLeet
TagsDisclaimersPrivacyTermsContactAbout Us

All Nodes Distance K in Binary Tree

Difficulty: Medium

Problem Description

Given the root of a binary tree, the value of a target node target, and an integer k, return an array of the values of all nodes that have a distance k from the target node. You can return the answer in any order.

Key Insights

  • The problem involves finding nodes at a specific distance from a given target node in a binary tree.
  • The binary tree structure allows for traversal in multiple ways (DFS or BFS).
  • A two-step approach is useful: first, identify the target node and create a mapping of each node to its parent, then perform a BFS or DFS to find all nodes at distance k from the target.

Space and Time Complexity

Time Complexity: O(N), where N is the number of nodes in the binary tree. Each node is visited once. Space Complexity: O(N), for storing the parent mapping and the result list.

Solution

To solve the problem, we use a combination of depth-first search (DFS) and breadth-first search (BFS). First, we traverse the tree to map each node to its parent. Then, we perform a BFS starting from the target node, exploring all nodes at a distance k by keeping track of the visited nodes.

Code Solutions

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

def distanceK(root, target, k):
    from collections import defaultdict, deque

    # Step 1: Create a parent mapping
    parent = {}
    
    def dfs(node, par):
        if node:
            parent[node] = par
            dfs(node.left, node)
            dfs(node.right, node)

    dfs(root, None)

    # Step 2: Perform BFS to find all nodes at distance k
    result = []
    queue = deque([target])
    visited = {target}

    while queue and k > 0:
        for _ in range(len(queue)):
            node = queue.popleft()
            for neighbor in (node.left, node.right, parent[node]):
                if neighbor and neighbor not in visited:
                    visited.add(neighbor)
                    queue.append(neighbor)
        k -= 1

    # Collect the result
    result = [node.val for node in queue]
    return result
← Back to All Questions