FastPrepClone a Binary Tree with Random Links
Problems/Clone a Binary Tree with Random Links

Clone a Binary Tree with Random Links

Expedia logoExpedia● MediumNEW GRADONSITE INTERVIEW

Updated Oct 2026

QuestionFunctionExamplesConstraints

Problem statement

Source note: The source requires a deep copy with left, right and random links, including duplicate values. The indexed-table representation and a post-copy mutation probe make independence observable in this practice interface. Estimated match 90%.

Node i is nodes[i]=[value,leftID,rightID,randomID]. IDs are row indices, -1 means no link, and node 0 is the root. Left and right links form a binary tree containing every row. Random links may point to any node, including themselves, and may form cycles. Values may repeat.

Make an independent copy of the complete node table, preserving every value and ID-labelled link. Then change only the original node at probeIndex: set its value to replacementValue and its random link to replacementRandom. The copied table must retain its pre-probe contents.

Return a matrix of 2N rows: the first N rows are the original table after the probe, and the last N rows are the copied table after the probe. Each half uses its own ID namespace 0..N-1; do not offset the copied link IDs. This finite observation distinguishes independent row copies from a shallow outer-array copy.

Function

cloneWithProbe(nodes: int[][], probeIndex: int, replacementValue: int, replacementRandom: int) → int[][]

Examples

Example 1

nodes = [[7,1,2,2],[7,-1,-1,0],[9,-1,-1,1]]probeIndex = 1replacementValue = 100replacementRandom = 2return = [[7,1,2,2],[100,-1,-1,2],[9,-1,-1,1],[7,1,2,2],[7,-1,-1,0],[9,-1,-1,1]]

Original node 1 changes, while copied node 1 retains value 7 and random ID 0. Equal values on nodes 0 and 1 do not merge their identities.

Example 2

nodes = [[4,-1,-1,0]]probeIndex = 0replacementValue = 5replacementRandom = -1return = [[5,-1,-1,-1],[4,-1,-1,0]]

The copied node keeps its original self-random link after the original loses that link.

Constraints

  • 1 <= nodes.length <= 200.
  • Each row has exactly 4 entries.
  • -1000000000 <= every table entry, replacementValue <= 1000000000.
  • 0 <= probeIndex <= 199.
  • -1 <= replacementRandom <= 199.
  • probeIndex and replacementRandom are smaller than nodes.length.
  • Columns 1 and 2 contain -1 or valid IDs and form one acyclic root-0 binary tree containing all rows. Column 3 is -1 or a valid node ID.

More Expedia Onsite Interview questions

  • Scramble StringONSITE INTERVIEW · Seen Sep 2026
  • Smallest Sufficient TeamONSITE INTERVIEW · Seen Sep 2026
  • Check Anagram Pairs Index by IndexONSITE INTERVIEW · Seen Oct 2025
  • Fresh Oranges Left After Rotting StopsONSITE INTERVIEW · Seen Oct 2025
  • Longest Increasing SubsequenceONSITE INTERVIEW · Seen Oct 2025
  • Lowest Common Ancestor with Repeated and Missing ValuesONSITE INTERVIEW · Seen Oct 2025
  • Shortest Substring with Exactly K OnesONSITE INTERVIEW · Seen Oct 2025
  • Middle Element of a Linked ListONSITE INTERVIEW · Seen Nov 2024
  • Minimum in a Rotated Sorted ArrayONSITE INTERVIEW · Seen Sep 2024
  • Mirror Image Binary TreesONSITE INTERVIEW · Seen Sep 2024

Similar questions at other companies

  • Top-Down Employee Reporting ForestOkta · ONSITE INTERVIEWOkta interview questions
  • Find the Root of a Directed TreeAmazon · ONSITE INTERVIEW
  • Everyone Under a ManagerAdobe · PHONE SCREENAdobe interview questions
  • N-ary Index-Path Encoder and DecoderBloomberg LP · PHONE SCREEN · ONSITE INTERVIEWBloomberg LP interview questions
  • Delete Nodes and Return Forest RootsGoogle · ONSITE INTERVIEWGoogle interview questions
  • In-Memory Filesystem CommandsPerplexity AI · PHONE SCREEN · ONSITE INTERVIEWPerplexity AI interview questions
  • Filter Undesired Comments and Their DescendantsReddit · PHONE SCREEN · ONSITE INTERVIEWReddit interview questions
  • JSON Path Lookup with Implicit Array WildcardsMongoDB · ONSITE INTERVIEWMongoDB interview questions
  • Validate and Resolve Evaluation ChainsPlaid · PHONE SCREEN · ONSITE INTERVIEWPlaid interview questions
  • Hierarchical Permission CheckeBay · ONSITE INTERVIEWeBay interview questions

Interview reports that mention this question

  • Expedia New Grad SDE Earlier Loops: 5 Experiences (Part 2 of 3)

Expedia interview experiences

  • Expedia Intern Final Round in 2021: 28 Experiences (Part 4 of 6)
  • Expedia Intern Finals Before 2020: 14 Experiences (Part 6 of 6)
  • Expedia Intern Final Round in 2020: 24 Experiences (Part 5 of 6)
  • Expedia Intern Final Round in 2022: 15 Experiences (Part 3 of 6)
  • Expedia Intern Final Round in 2023: 17 Experiences (Part 2 of 6)
All Expedia interview questionsSee Expedia hiring insights
Saved
class Solution {
    public int[][] cloneWithProbe(int[][] nodes, int probeIndex, int replacementValue, int replacementRandom) {
        // Write your code here.
    }

}
Checking account…