[daily coding problem] Counting Unival Subtrees

problem

code

public class UnivalTree {
    public Node root;

    public class Node {
    	public String value;
    	public Node left;
        public Node right;        
    }
    
    public boolean isUnival(Node root, value) {
    	if(root.value == null) return true;
        if (root.value = value)
        	return isUnival(root.left, value) && 
            			isUnival(root.right, value); 
        return false;
    }
    
    public int countUnivalTree(Node root) {
    	if (root == null)
            return 0;
		int left = countUnivalTree(root.left);
        int right = countUnivalTree(root.right);
        if (isUnival(root)) return 1 + left + right;
		else return left + right;        
    }
    
    public static void main(String ...args) {
    	UnivalTree u = new UnivalTree();
        u.root = new Node();
        u.root.value = 'a';
        u.root.right = new Node();
        u.root.left = new Node();
        
        int count = u.countUnivalTree(u.root);
        System.out.println(count);        
    }
    
}

Time: O(n^2), cuz every time check if root is a unival tree, need to evalueate subtrees
Space: O(1)

• Better solution
  what if count unival tree from each leaf?

const isUnival = root => {
  if (root == undefined) return [0, true];
  const [left, isLeftUnival] = isUnival(root.left);
  const [right, isRightUnival] = isUnival(root.right);
  let totalCount = left + right;
  
  if (isLeftUnival && isRightUnival) {
  	if (root.left != undefined && root.value != root.left.value)
      return [totalCount, false];
    if (root.right != undefined && root.value != root.right.value)
      return [totalCount, false];
    
    totalCount += 1;
    return [totalCount, true];
  }
  
  return [totalCount, false];
}

Time: O(n)
Space: O(1)

Example2) explanation
Unival tree count = 5

no/ = undefined

level1 a [1+4, false]
level2 c b [[0+0+1, true], [1+2+1, true]]
level3 no/ no/ b b [-, -, [0+0+1, true],[0+1+1, true]]
level4 no/ no/ no/ no/ no/ no/ no/ b [-, -, -, -, -, -, -, [0+0+1, True]]