Path Between Two Nodes of a Binary Tree
Updated
Problem statement
You are given the root of a binary tree whose node values are all different, and two of those values, startValue and destValue. One step moves from a node to its left child (L), to its right child (R) or to its parent (U).
Return the shortest sequence of steps that leads from the node with value startValue to the node with value destValue, written as a string of the letters L, R and U. In a tree there is only one shortest route, so the answer is unique.
Function
stepDirections(root: TreeNode, startValue: int, destValue: int) → StringExamples
Example 1
root = [7,3,11,1,5,9,14,null,null,4,6]startValue = 4destValue = 9return = "UUURL"From 4, go up to 5, up to 3 and up to the root 7 (three U steps). Then go right to 11 and left to 9. Answer: "UUURL".
Example 2
root = [2,8,6,null,1,null,null,3]startValue = 2destValue = 3return = "LRL"The start 2 is the root and an ancestor of 3, so no U step is needed: left to 8, right to 1, left to 3. Answer: "LRL".
Example 3
root = [10,20,30,40]startValue = 40destValue = 10return = "UU"The destination 10 is an ancestor of 40: go up twice, through 20. Answer: "UU".
Constraints
- The tree has between
2and500nodes. 1 <= node.val <= 10^4, and all node values are differentstartValueanddestValueare values of nodes in the tree, andstartValue != destValue
More Adobe Phone Screen questions
- Evaluate a Parenthesized Integer ExpressionPHONE SCREEN · Seen Oct 2026
- All Elements of Two BSTs in OrderPHONE SCREEN · Seen Aug 2026
- Rotate an Array In PlaceOA · PHONE SCREEN · Seen Aug 2026
- Binary Tree Level-Order Traversal by LevelsPHONE SCREEN · ONSITE INTERVIEW · Seen Aug 2026
- Count Occurrences in a Sorted ArrayPHONE SCREEN · ONSITE INTERVIEW · Seen Jul 2026
- Count Pairs with Absolute Difference KPHONE SCREEN · Seen Jul 2026
- Count Subsets with Sum KPHONE SCREEN · Seen Jul 2026
- Numbers with Exactly Three DivisorsPHONE SCREEN · Seen Jul 2026
- Sum of Even Nodes on a Path in a Numbered Binary TreePHONE SCREEN · Seen Jul 2026
- Largest Value in Every Sliding WindowPHONE SCREEN · Seen Jul 2026
Similar questions at other companies
- Account Roles With Parent-User InheritanceStripe · PHONE SCREENStripe interview questions
- Find All Paths for a Name in a File SystemThe Walt Disney Company · PHONE SCREENThe Walt Disney Company interview questions
- Filesystem Hash TreeCursor · PHONE SCREEN · ONSITE INTERVIEWCursor interview questions
- Canonical N-Ary Tree CodecApple · PHONE SCREENApple interview questions
- Find File Paths in a Directory TreeUber · PHONE SCREENUber interview questions
- Count Distinct Rooted-Tree GraftsThe D.E. Shaw Group · PHONE SCREENThe D.E. Shaw Group interview questions
- Serialize and Deserialize a Binary TreeNVIDIA · PHONE SCREENNVIDIA interview questions
- Print All File and Folder PathsNutanix · PHONE SCREENNutanix interview questions
- JSON Path Lookup with Implicit Array WildcardsMongoDB · ONSITE INTERVIEWMongoDB interview questions
- Serialize and Deserialize a Binary TreeGoogle · ONSITE INTERVIEWGoogle interview questions
Interview reports that mention this question
Adobe interview experiences
- Adobe Web, QA, DevOps, ML Roles: 13 Experiences (Part 3 of 3)
- Adobe SWE Interviews, Level Unknown: 25 Experiences (Part 2 of 3)
- Adobe Interviews, Level Unknown: 38 Experiences (Part 1 of 3)
- Adobe New Grad MTS Interview Questions: 7 Experiences
- Adobe ML/Research Intern Interviews: 12 Experiences (Part 4 of 4)