All problems

Message Hops

Medium · tree dfs

In a company, messages only travel along reporting lines: from an employee to one of their direct reports, or from an employee to their direct manager. The org chart is a binary tree given by its root (the head of the company). Each employee has at most two direct reports, and every employee has a different identification number, stored as the node's value.

Two employees, with numbers a and b, want to exchange a message. A hop is one step from an employee to a direct report or to a direct manager. Return the smallest number of hops a message needs to get from a to b.

If either number does not belong to anyone in the chart, return -1. The two numbers are always different.

Examples

Example 1

Input: root = [10, 4, 15, 2, 7, null, 20, 1], a = 1, b = 7

Output: 3

The message goes 1, 2, 4, 7: up to employee 2, up to 4, then down to 7.

Example 2

Input: root = [10, 4, 15, 2, 7, null, 20, 1], a = 4, b = 1

Output: 2

Employee 4 manages 2, who manages 1, so the message only goes down.

Example 3

Input: root = [10, 4, 15, 2, 7, null, 20, 1], a = 1, b = 99

Output: -1

Nobody has number 99.

Constraints