Problem 456808 · easy · Level 04 Non-Linear Data Structures

Univalued Tree

binary trees · traversal · predicates

A binary tree is univalued if every node holds the same value. Given the root, return True if the tree is univalued and False otherwise. An empty tree counts as univalued.

Examples

      1
     / \
    1   1
   / \   \
  1   1   1

Input:  root = build_tree([1, 1, 1, 1, 1, None, 1])
Output: True

      2
     / \
    2   2
   / \
  5   2

Input:  root = build_tree([2, 2, 2, 5, 2])
Output: False

Constraints

  • 0 <= number of nodes <= 2000
  • -10**4 <= node.val <= 10**4
  • Target complexity: O(n) time.

Goals

  • Carry a reference value through the traversal
  • Stop early on the first mismatch
  • Decide the answer for an empty tree
Starting Python…