Katkat
Back

Solve coding and AI-assisted tasks

MetaBackend Engineer · Onsite
MediumBackend EngineerOnsiteCoding & Algorithms

Last updated

This problem tests your ability to manipulate tree structures with parent pointers and verify path validity under specific movement constraints.

Problem: Tree Path Validation with Parent Pointers

You are given a binary tree where each node contains a value and a reference to its parent. You are tasked with determining if a given sequence of node values represents a valid root-to-leaf path.

A path is valid if:

  1. The first node in the sequence is the root of the tree.
  2. The last node in the sequence is a leaf (both left and right children are null).
  3. Each consecutive pair of nodes in the sequence exists as a parent-child relationship in the tree.

Node Structure

class Node:
    def __init__(self, val, left=None, right=None, parent=None):
        self.val = val
        self.left = left
        self.right = right
        self.parent = parent

Function Signature

def is_valid_path(root, sequence):
    """
    :param root: Node, the root of the tree
    :param sequence: List[int], values representing the path
    :return: bool
    """

Example 1

Input: Root (1) -> left (2), right (3). Sequence: [1, 2] Output: True Explanation: 1 is the root, 2 is a leaf, and 2 is a child of 1.

Example 2

Input: Root (1) -> left (2). Sequence: [1, 3] Output: False Explanation: 3 is not a child of 1.

Constraints

  • Number of nodes: 1 to 10^5
  • Sequence length: 1 to 10^5
  • Tree nodes contain unique values.
  • Time complexity target: O(N) where N is the length of the sequence.

Hints

Hint 1

Since you are given the root, you can perform a recursive or iterative traversal to map values to nodes if the sequence nodes are provided as references; if they are just integers, use a hash map to look up nodes by value.

Hint 2

Verify the sequence step-by-step: check if `sequence[i]` is a direct child of `sequence[i-1]`.

Hint 3

Remember to explicitly check if the final node in your sequence is actually a leaf node in the tree structure.

Follow-up questions

  • How would you modify your solution if the tree contained duplicate values, making the integer sequence ambiguous?
  • If you were given a node deep in the tree and needed to find the root, how would the parent pointers simplify this compared to a standard binary tree?
  • What is the space complexity of your solution, and can you optimize it if you are constrained by recursion depth?