All Nodes Distance K in Binary Tree

All Nodes Distance K in Binary Tree is a Medium Data Structures and Algorithms interview problem you can solve, run and submit on Thita.ai. It belongs to the Tree Traversal Patterns (DFS & BFS) pattern, in the Recursive Postorder Traversal subpattern.

Problem statement

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 1:

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.

Example 2:

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

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

Topics and companies

Topics: Hash Table, Tree, Depth-First Search, Breadth-First Search, Binary Tree.

Reported in interviews at Amazon, Facebook, Google, Microsoft.

How to practise All Nodes Distance K in Binary Tree on Thita.ai

Starter code is provided in C, C#, C++, Go, Java, JavaScript and Python. Your solution runs against 5 test cases for this problem, with the AI coach available for a hint when you are stuck rather than a finished answer. The reference solution runs in O(N), where N is the number of nodes in the tree. Building the graph takes O(N), and BFS visits each node at most once. time and O(N), for the adjacency list (neighbors), visited set, and BFS queue/levels. space.

Open All Nodes Distance K in Binary Tree in the code editor, or read the All Nodes Distance K in Binary Tree editorial for a worked solution with its approach and complexity analysis.

Where All Nodes Distance K in Binary Tree sits in the DSA pattern sheet

• Tree Traversal Patterns (DFS & BFS) pattern guide
• Recursive Postorder Traversal subpattern
• The full DSA patterns sheet
• All coding practice problems

Problems related to All Nodes Distance K in Binary Tree

Other problems that use the same Recursive Postorder Traversal and Tree Traversal Patterns (DFS & BFS) techniques:

• Balanced Binary Tree — Easy, same subpattern
• Binary Tree Maximum Path Sum — Hard, same subpattern
• Binary Tree Postorder Traversal — Easy, same subpattern
• Delete Nodes And Return Forest — Medium, same subpattern
• Diameter of Binary Tree — Easy, same subpattern
• Find Leaves of Binary Tree — Medium, same subpattern