Asked inNagarro,SDE

Duplicate Subtrees Problem Statement

Given a binary tree, return the root values of all duplicate subtrees. Two subtrees are considered duplicate if they have the same structure with identical node values. For each duplicate subtree, return the root value of any one of them.

Example:

Tree:
 Consider the following binary tree: alt text 
Output:
{2, 3}
Explanation:

The duplicate subtrees are {{2, 3}, {3}}, hence the root values are {2, 3}. The order doesn't matter.

Input:

T, then each test case with nodes in level order, using -1 for null nodes.
Example for one tree: 1 2 3 4 -1 5 6 -1 7 -1 -1 -1 -1 -1 -1

Output:

Space-separated root values of all duplicate subtrees for each test case in separate lines. Use -1 if no duplicates.

Constraints:

  • 1 <= T <= 5
  • 1 <= N <= 100
  • 1 <= val <= 105
  • Time Limit: 1 sec
Note:
The input for the tree is given as a single sequence of space-separated values.
AnswerBot
4d

Find root values of duplicate subtrees in a binary tree.

  • Traverse the tree in a bottom-up manner to identify duplicate subtrees.

  • Use a hashmap to store the subtree structures and their frequencies.

  • Retur...read more

Help your peers!
Add answer anonymously...
Nagarro SDE Interview Questions
Stay ahead in your career. Get AmbitionBox app
qr-code
Helping over 1 Crore job seekers every month in choosing their right fit company
65 L+

Reviews

4 L+

Interviews

4 Cr+

Salaries

1 Cr+

Users/Month

Contribute to help millions

Made with ❤️ in India. Trademarks belong to their respective owners. All rights reserved © 2024 Info Edge (India) Ltd.

Follow us
  • Youtube
  • Instagram
  • LinkedIn
  • Facebook
  • Twitter