# Counting Unival Subtrees

This interesting interview problem was asked by Google.

A unival tree (which stands for “universal value”) is a tree where all nodes have the same value.

Given the root to a binary tree, count the number of unival subtrees.

Before we solve this, you should take some time to think about it first!

To start off, we should go through some examples.

1 | a |

This tree has 3 unival subtrees: the two ‘a’ leaves and the one ‘A’ leaf. The ‘A’ leaf causes all its parents to not be counted as a unival tree, however.

1 | a |

This tree has 5 unival subtrees: the leaf at ‘c’, and every ‘b’.

We can start off by first writing a function that checks whether a tree is unival or not. Then, perhaps we could use this to count up all the nodes in the tree.

To check whether a tree is a unival tree, we must check that every node in the tree has the same value. To start off, we could define an `is_unival`

function that takes in a root to a tree. We would do this recursively with a helper function. Note that a leaf qualifies as a unival tree.

1 | def is_unival(root): |

And then our function that counts the number of subtrees could simply use that function:

1 | def count_unival_subtrees(root): |

However, this runs in O(n^2) time. For each node of the tree, we’re evaluating each node in its subtree again as well. We can improve the runtime by starting at the leaves of the tree, and keeping track of the unival subtree count and value as we percolate back up. This should evaluate each node only once, making it run in O(n) time.

1 | def count_unival_subtrees(root): |

Are you interviewing for programming jobs, or do you just enjoy fun programming questions? Check out our newsletter, Daily Coding Problem, to get a question in your inbox every day.

Thanks for reading! I hope this was interesting. Good luck on your interviews!

# Ace your programming interview

Get a coding problem every day in your inbox!