CareerCup

First Approach: Perform a dfs or bfs on the tree and retrieve the results. Check whether all of them are the same element. Second approach: As you are traversing, use a set or hash map to make sure they are all the same elements and if they are different return False.

Simple solution in Python outlining the first approach:

def preOrderRecursive(root):
  res = []
  def helper(root, res):
    if not root:
      return

    res.append(root.val)
    for child in root.children:
      helper(child, res)

  helper(root, res)
  return res

def isUnivalTree(root):
  result = preOrderRecursive(root)
  return all(result[0] == x for x in result[1:])

Test code:

class Node:
  def __init__(self, val):
    self.val = val
    self.children = []

'''
Construct the following tree:
            1
          / | \
        1   2  1
            /\  \
            1 3  1
'''
root = Node(1)
root.children = [Node(1), Node(2), Node(1)]
root.children[1].children = [Node(1), Node(3)]
root.children[2].children = [Node(1)]
print(isUnivalTree(root)) # Output: False

'''
Construct the following tree:
            1
          / | \
        1   1  1
            /\  \
            1 1  1
'''
root = Node(1)
root.children = [Node(1), Node(1), Node(1)]
root.children[1].children = [Node(1), Node(1)]
root.children[2].children = [Node(1)]
print(isUnivalTree(root)) # Output: True

Java

public boolean isUnivalTree (TreeNode root)
    {
        int value = root.children.isEmpty() ? root.val : root.children.get(0).val;
        boolean result = true;
        if (root==null) return false;
        for (TreeNode node : root.children)
        {
            result = result & (node.val==value) & isUnivalTree(node);
        }
        return result;
    }