InternDoor

The way down to a value

Mediumtrees · depth-first search · backtracking

Reported in interviews at (where)

Every value in the binary tree is different, and target is one of them.

Return the values on the path from the root down to the node holding target, starting with the root's value and ending with target.

Example 1
Input
root = [7,2,9,4,null,null,1,8]
target = 8
Output
[7,2,4,8]

8 is the left child of 4, which is the left child of 2, the root's left child.

Example 2
Input
root = [3,1]
target = 3
Output
[3]

The target is the root itself.

Limits

  • 1 <= number of nodes <= 20000
  • -100000 <= Node.val <= 100000
  • all values are different
  • target is the value of a node in the tree
  • the tree is at most 3000 levels deep

Hints

Hint 1

Search depth-first, adding each node to a list on the way down.

Hint 2

When neither subtree of a node holds the target, take the node off the end of the list before going back up.

Where this was reported

Our own problem on the task these candidates describe; the wording, examples and tests are InternDoor’s.

Run your code to check it on the examples. Submit runs every hidden test.

Ready for the real one?

Engineering internships and entry-level jobs in India, newest first.