Solution


Intuition

Given a node in our tree, we know that it is a univalue subtree if it meets one of the following criteria:

  1. The node has no children (base case)
  2. All of the node's children are univalue subtrees, and the node and its children all have the same value

With this in mind we can perform a depth-first-search on our tree, and test if each subtree is uni-value in a bottom-up manner.

!?!../Documents/250_Count_Univalue_SUbtrees.json:1000,518!?!

Algorithm

Complexity Analysis

  • Time complexity : .

    Due to the algorithm's depth-first nature, the is_uni status of each node is computed from bottom up. When given the is_uni status of its children, computing the is_uni status of a node occurs in

    This gives us time for each node in the tree with total nodes for a time complexity of

  • Space complexity : , with H being the height of the tree. Each recursive call of is_uni requires stack space. Since we fully process is_uni(node.left) before calling is_uni(node.right), the recursive stack is bound by the longest path from the root to a leaf - in other words the height of the tree.


Approach 2: Depth First Search - Pass Parent Values

Algorithm

We can use the intuition from approach one to further simplify our algorithm. Instead of checking if a node has no children, we treat null values as univalue subtrees that we don't add to the count.

In this manner, if a node has a null child, that child is automatically considered to a valid subtree, which results in the algorithm only checking if other children are invalid.

Finally, the helper function checks if the current node is a valid subtree but returns a boolean indicating if it is a valid component for its parent. This is done by passing in the value of the parent node.

The above code is a commented version of the code here, originally written by Stefan Pochmann.

Complexity Analysis

  • Time complexity : . Same as the previous approach.

  • Space complexity : , with H being the height of the tree. Same as the previous approach.



Written by @alwinpeng.