FastPrepCompare N-Ary Tree Leaf Sequences

Compare N-Ary Tree Leaf Sequences

Navan logoNavan● MediumFULLTIMEONSITE INTERVIEW
Learn

Problem statement

Each N-ary tree is represented by parallel parent and values arrays. The root has parent -1; every other entry names its parent index. Children are ordered by node index. Return whether the two trees have identical leaf-value sequences from left to right. Use an iterative traversal.

Function

sameNaryLeafValues(parent1: int[], values1: int[], parent2: int[], values2: int[]) → boolean

Examples

Example 1

parent1 = [-1,0,0]values1 = [1,2,3]parent2 = [-1,0,0]values2 = [7,2,3]return = true

Both leaf sequences are [2,3].

Example 2

parent1 = [-1,0,0]values1 = [1,2,3]parent2 = [-1,0,0]values2 = [1,3,2]return = false

Leaf order differs.

Constraints

  • Each tree has between 1 and 200000 nodes.
  • Each input is a valid rooted tree with exactly one -1 parent.
  • Node values fit in a signed 32-bit integer.

More Navan problems

See Navan hiring insights
public boolean sameNaryLeafValues(int[] parent1, int[] values1, int[] parent2, int[] values2) {
    // Write your code here.
}
parent1[-1,0,0]
values1[1,2,3]
parent2[-1,0,0]
values2[7,2,3]
expectedtrue
Checking account…