All Nodes Distance K in Binary Tree — LeetCode 863 Python Solution
MediumTreeDepth-First SearchBreadth-First SearchHash TableBinary Tree
- Problem
- #863
- Pattern
- Tree Traversal
- Reading time
- 6 min
- Source
- leetcode.com
The problem
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.
Example
- Input
- root = [3,5,1,6,2,0,8,null,null,7,4], target = 5, k = 2
- Output
- [7,4,1]
- Explanation
- The nodes that are a distance 2 from the target node (with value 5) have values 7, 4, and 1.
Python solution
Python
# 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 ansComplexity
| Measure | Complexity |
|---|---|
| Time | O(n) |
| Space | O(n) auxiliary |
Pattern: Tree Traversal
Choose the order — preorder, inorder, postorder, level — and the problem solves itself. LeetCode 863. All Nodes Distance K in Binary Tree is filed here because LeetCode tags it Tree and Binary Tree, which is the vocabulary this hub collects.
The tree traversal guide has the Python template for the pattern and the 225 LeetCode problems that use it.
Related problems
LeetCode 865Smallest Subtree with all the Deepest NodesMediumLeetCode 653Two Sum IV - Input is a BSTEasyLeetCode 987Vertical Order Traversal of a Binary TreeHardLeetCode 1123Lowest Common Ancestor of Deepest LeavesMediumLeetCode 1261Find Elements in a Contaminated Binary TreeMediumLeetCode 2385Amount of Time for Binary Tree to Be InfectedMedium
Frequently asked questions
- How hard is LeetCode 863. All Nodes Distance K in Binary Tree?
- LeetCode 863. All Nodes Distance K in Binary Tree is rated Medium on LeetCode.
- What is the time complexity of LeetCode 863. All Nodes Distance K in Binary Tree?
- The Python solution on this page runs in O(n).
- What is the space complexity of LeetCode 863. All Nodes Distance K in Binary Tree?
- The Python solution on this page uses O(n) auxiliary space.
- What topics does LeetCode 863. All Nodes Distance K in Binary Tree cover?
- LeetCode 863. All Nodes Distance K in Binary Tree is tagged Tree, Depth-First Search, Breadth-First Search, Hash Table and Binary Tree on LeetCode.