Unival Trees — Asked in Google and Amazon Interview

Problem Statement :

You are given a binary tree. Return the count of unival sub-trees in the given binary tree. In unival trees, all the nodes, below the root node, have the same value as the data of the root.

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 on its place.

Sample Input:

1 2 3 2 -1 3 4 -1 -1 3 3 -1 -1 -1 -1 -1 -1

Sample Output:

6

Approach :

Bottom-Up Approach

In this approach, we will count the number of unival subtrees in a bottom-up manner. This means we will calculate the count of unival subtrees from left and right subtrees and also calculate whether they are themselves unival or not. Now for each node to be visited, the tree with root as the current node is unival if and only if both the left and right subtree is unival and the values of left and right child(if exists) should also be equal to the value of the current node. So if these conditions are satisfied we will increment the total count and return this value and a true boolean value to denote the count of unival nodes and that the current node is also unival. Otherwise, we will return the total count(without incrementing) with a false boolean value denoting that the given current subtree is not unival.

Time Complexity : O(N)
Space Complexity : O(N)

Code :

Thanks for Reading

Placewit grows the best engineers by providing an interactive classroom experience and by helping them develop their skills and get placed in amazing companies.

Learn more at Placewit. Follow us on Instagram and Facebook for daily learning.