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.
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.
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.
And then our function that counts the number of subtrees could simply use that function:
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.
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!