Find path between two nodes in a binary tree
Company: Ripple
Role: Software Engineer
Category: Coding & Algorithms
Difficulty: hard
Interview Round: Technical Screen
## Problem
Given a binary tree and two target nodes `a` and `b`, return the **simple path** from `a` to `b` (inclusive) as an ordered list of node values.
- The path should list nodes in the order you would visit them when traveling from `a` to `b` along parent/child links.
- You may assume the tree nodes have fields like `val`, `left`, and `right`.
### Example 1
Tree:
```
1
/ \
2 3
```
Input: `a = 2`, `b = 3`
Output: `[2, 1, 3]`
### Example 2
Tree:
```
1
/ \
2 3
/ \
6 5
/ \
7 8
```
Input: `a = 3`, `b = 5`
Output: `[3, 1, 2, 5]`
## Requirements
- Define what your function receives for `a` and `b` (e.g., node references/pointers, unique IDs, or values).
- Handle cases where one node is the ancestor of the other.
- Clarify behavior if one or both targets are not present (e.g., return empty list or error).
## Follow-ups
1. **Duplicate values:** If the tree can contain duplicate values, how does your approach change? What should be used to identify `a` and `b`?
2. **BST variant:** If the tree is a Binary Search Tree, what (if anything) changes in:
- the algorithm,
- and the time complexity (compared to a general binary tree)?
Quick Answer: This question evaluates understanding of tree data structures, traversal and path reconstruction techniques, including reasoning about lowest common ancestors, ancestor–descendant relationships, duplicate identification, and handling absent targets.
Given a unique-valued level-order tree, return the simple path from value a to value b.
Constraints
- None represents a missing node; values are unique
Examples
Input: ([1, 2, 3], 2, 3)
Expected Output: [2, 1, 3]
Explanation: Prompt example.
Input: ([1, 2, 3, 6, 5, None, None, 7, 8], 3, 5)
Expected Output: [3, 1, 2, 5]
Explanation: Crosses root then left subtree.