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.
1 2 3 2 -1 3 4 -1 -1 3 3 -1 -1 -1 -1 -1 -1
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)