cswork / libraryOpen practice workspace

Coding questions · Ripple

Find path between two nodes in a binary tree

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.

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)?

Path Between Two Nodes in a Binary Tree

Constraints

  • None represents a missing node; values are unique