treebinarysubtree

Single value binary tree

I am going through this problem on binary trees and it says that the following tree has 5 same-value subtrees. I am only seeing 2 subtrees with 5 value and 3 subtrees with 4 value. How are there 5 subtrees with the same value. What am I missing?

The definition provided for single values subtrees: A Single Valued Subtree is one in which all the nodes have same value.

          5
         / \
        4   5
       / \   \
      4   4   5
Solution

  • You have to take into considerations and the leaves alone as well, they are bassically a subtree as well, but with only one node, so you have 5 in total:

        4     5    4   4   5
   / \     \ 
  4   4     5