De Shaw SWE(L60) Interview | 75Lakhs CTC
- Posted
- 12 Oct 2026
Summary
I was presented with a tree merging problem in the D. E. Shaw software engineering interview.
How it went
You are given two rooted trees, Tree 1 and Tree 2, containing N1 and N2 nodes, respectively. The nodes in each tree are numbered from 1, and node 1 is the root of both trees.
You must perform the following operation exactly once:
Choose any node U in Tree 2.
Remove the subtree rooted at U, including U and all its descendants, from Tree 2.
Attach this entire subtree to any leaf of Tree 1 by making U a child of that leaf.
Discard all remaining nodes of Tree 2 and keep only the modified Tree 1.
Your task is to determine the number of distinct rooted tree structures that can be obtained after performing this operation.
Important Notes You may choose any node in Tree 2, including its root.
The subtree must be attached to a leaf of Tree 1.
Two resulting trees are considered identical if one can be transformed into the other by reordering the children of any node and renumbering all non-root nodes.
In other words, node labels and the order of children do not matter; only the rooted tree structure matters.
Different choices of nodes or attachment points may produce the same tree structure. Such trees must be counted only once.
Questions asked (1)
- 01
Count Distinct Rooted Trees after Merging Subtree
Data Structures & Algorithms
You are given two rooted trees, Tree 1 and Tree 2, containing N1 and N2 nodes, respectively. The nodes in each tree are numbered from 1, and node 1 is the root of both trees.
You must perform the following operation exactly once:
Choose any node U in Tree 2.
Remove the subtree rooted at U, including U and all its descendants, from Tree 2.
Attach this entire subtree to any leaf of Tree 1 by making U a child of that leaf.
Discard all remaining nodes of Tree 2 and keep only the modified Tree 1.
Your task is to determine the number of distinct rooted tree structures that can be obtained after performing this operation.
Important Notes:
- You may choose any node in Tree 2, including its root.
- The subtree must be attached to a leaf of Tree 1.
- Two resulting trees are considered identical if one can be transformed into the other by reordering the children of any node and renumbering all non‑root nodes.
- Node labels and the order of children do not matter; only the rooted tree structure matters.
- Different choices of nodes or attachment points may produce the same tree structure, which should be counted only once.