Solution to Leetcode problem 965 Univalued Binary Tree

This is an easy problem to start with contest 117. You are given a binary tree T, where each node n contains a value val. If all the values in T are the same, return true, otherwise false.

There are two main approaches we could pursue here. The first one is a recursive approach similar to a depth first search. The second one is a breadth first search in a more iterative style. Very often, with tree problems, one is better than the other, but in this case both approaches with work just fine. Therefore, let’s do both of them!

In the first approach, we take the value of the root as base value, and then recursively check that all the node values in the tree match the root value. Here is a Java solution for the first approach:

/**
 * Definition for a binary tree node.
 * public class TreeNode {
 *   int val;
 *   TreeNode left;
 *   TreeNode right;
 *   TreeNode(int x) { val = x; }
 * }
 */
class Solution {
  public boolean isUnivalTree(TreeNode root) {
    if (root == null) {
      // This first check is actually unnecessary to solve the 
      // Leetcode problem since it specifies that the tree has at 
      // least one node. However, it is useful in the general case 
      // to prevent a null pointer exception.
      return true;
    } else {
      return isUnivalTree(root, root.val);
    } 
  }
  public boolean isUnivalTree(TreeNode root, int val) {
    return (root == null) 
        || (root.val == val 
            && isUnivalTree(root.left, val) 
            && isUnivalTree(root.right, val));
  }
}

In the second approach, also take the root value as a base, but we use a queue and check the value of the nodes in a different order (BFS). Here is a Java solution for the second approach.

/**
 * Definition for a binary tree node.
 * public class TreeNode {
 *   int val;
 *   TreeNode left;
 *   TreeNode right;
 *   TreeNode(int x) { val = x; }
 * }
 */
class Solution {
  public boolean isUnivalTree(TreeNode root) {
    if (root == null) {
      // This first check is actually unnecessary to solve the 
      // Leetcode problem since it specifies that the tree has at 
      // least one node. However, it is useful in the general case 
      // to prevent a null pointer exception.
      return true;
    } else {
      return isUnivalTree(root, root.val);
    } 
  }
    
  public boolean isUnivalTree(TreeNode root, int val) {
    Queue<TreeNode> queue = new LinkedList<>();
    queue.add(root);
    while(!queue.isEmpty()) {
      TreeNode n = queue.remove();
      if (n.val != val) {
        return false;
      }
      if (n.left != null) {
        queue.add(n.left);
      }
      if (n.right != null) {
        queue.add(n.right);
      }
    }
    // We went through all the nodes and they all matched the 
    // value of the root, return true
    return true;
  }
}

PS: All revenue made from all what I publish through Medium will be given to charities, so keep reading :)