Unival Trees Problem Statement

You are given a binary tree. Your task is to return the count of unival sub-trees in the given binary tree. In a unival tree, all nodes below the root node have the same value as the root node.

Example:

Consider the binary tree given in the following diagram, the number of unival trees is 5.

alt-text

Input:

The first line of input contains an integer T, the number of test cases.

The next T lines, where each line contains elements in level order form. The input consists of values of nodes separated by a single space in a single line. In case a node is null, we take -1 in its place.

For example, the input for the tree depicted in the below image would be:
1
2 3
4 -1 5 6
-1 7 -1 -1 -1 -1
-1 -1

alt text

Output:

For every test case, print a single line containing an integer, i.e., the count of unival trees.

Example:

Input:
1
1 2 3 4 -1 5 6 -1 7 -1 -1 -1 -1 -1 -1

Output:
5

Constraints:

  • 1 <= T <= 10
  • 0 <= N <= 10^5
  • 0 <= data <= 10^4, where data is the value for a node.
  • Time Limit: 1 sec

Note:

The above format was just to provide clarity on how the input is formed for a given tree. The sequence will be put together in a single line separated by a single space. Hence, for the above depicted tree, the input will be given as:
1
1 2 3 4 -1 5 6 -1 7 -1 -1 -1 -1 -1 -1

You do not need to print anything; it has already been taken care of. Just implement the given function.
AnswerBot
1d

Count the number of unival sub-trees in a binary tree where all nodes below the root have the same value as the root node.

  • Traverse the binary tree recursively and check if each subtree is a unival tre...read more

Help your peers!
Add answer anonymously...
Infosys Software Developer 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