Binary Tree Search Function

MediumPython

Problem

Nintendo eShop services represent one search index as a binary tree of nodes. Given the root and a target value, return the path to the nearest matching node.

A path is an array containing "L" and "R", where each entry indicates moving to the left or right child. If multiple nodes contain the target at the same minimum depth, return the lexicographically smallest path, treating "L" < "R". Return None when no node matches.

Formal Specification

Implement search_binary_tree(tree, target).

tree is either None or a nested dictionary with keys value, left, and right.
value and target are integers.
Each child is another node dictionary or None.
The output is a list of direction strings, or None if the target is absent.
Duplicate values are allowed.
The input is a proper tree, so nodes have at most one parent.

Use an algorithm that finds the shallowest match and avoids storing a complete path for every queued node.

Constraints

0 <= number of nodes <= 10^5
-10^9 <= node.value, target <= 10^9
The tree height may be 10^5
Duplicate values are allowed
The input is a proper binary tree
The tree is not necessarily a binary search tree

Function Signature

def search_binary_tree(tree, target):

Nintendo eShop services represent one search index as a binary tree of nodes. Given the root and a target value, return the path to the nearest matching node.

Formal Specification

Implement search_binary_tree(tree, target).

tree is either None or a nested dictionary with keys value, left, and right.
value and target are integers.
Each child is another node dictionary or None.
The output is a list of direction strings, or None if the target is absent.
Duplicate values are allowed.
The input is a proper tree, so nodes have at most one parent.

Use an algorithm that finds the shallowest match and avoids storing a complete path for every queued node.