Combinatorics › Counting principles › Bits and binary trees

Count unival subtrees in a tree

High school · ●●○○○ 20 pts

A unival subtree of a binary tree is a subtree in which all nodes have the same value. A single leaf counts as a unival subtree. Consider the following binary tree. The root has value

0

. The root's left child has value

1

and is a leaf. The root's right child has value

0

; its left child has value

1

and its right child has value

0

(a leaf). The node with value

1

(the left child of the right child) has two children, both with value

1

(leaves). How many unival subtrees does the tree have?

binary trees recurrence relations