Univalued Binary Tree

Easy
1883.

Univalued Binary Tree

Univalued Binary Tree is an easy coding problem on depth-first search, breadth-first search and trees, asked in Amazon interviews.

A binary tree is uni-valued if every node in it holds the same value.

Given the root of a binary tree, return true if the tree is uni-valued, and false otherwise.

Example 1

Input
root = [1,1,1,1,1,null,1]
Output
true
Explanation
Every node holds 1.

Example 2

Input
root = [2,2,2,5,2]
Output
false
Explanation
One node holds 5.

Example 3

Input
root = [7]
Output
true
Explanation
A single node is trivially uni-valued.

Constraints

  • 1 <= number of nodes <= 100
  • 0 <= Node.val < 100
Write your solution here. Running it against the tests needs a free account — what you type comes with you.Sign in to run
/**
 * Definition for a binary tree node (provided by the judge — do not redefine it):
 * function TreeNode(val, left, right) {
 *     this.val = (val===undefined ? 0 : val)
 *     this.left = (left===undefined ? null : left)
 *     this.right = (right===undefined ? null : right)
 * }
 */
/**
 * @param {TreeNode} root
 * @return {boolean}
 */
var isUnivalTree = function(root) {
    // Write your code here
    
};

Sign in to run your own test cases

Sign in

Univalued Binary Tree — Solution in Python, Java & C++

Univalued Binary Tree solution explained: step-by-step approach, complexity and code in Python, Java, C++ and JavaScript. An easy problem, asked at Amazon.

Univalued Binary Tree is an easy coding problem on depth-first search, breadth-first search and trees, asked in Amazon interviews.

Problem statement

A binary tree is uni-valued if every node in it holds the same value.

Given the root of a binary tree, return true if the tree is uni-valued, and false otherwise.

Example 1

Input: root = [1,1,1,1,1,null,1]
Output: true
Explanation: Every node holds 1.

Example 2

Input: root = [2,2,2,5,2]
Output: false
Explanation: One node holds 5.

Example 3

Input: root = [7]
Output: true
Explanation: A single node is trivially uni-valued.

Constraints

  • 1 <= number of nodes <= 100
  • 0 <= Node.val < 100

Hints for Univalued Binary Tree

  1. Hint 1

    If the tree is uni-valued, the shared value must be the root's.

  2. Hint 2

    Visit every node and compare it with the root's value.

  3. Hint 3

    Stop at the first node that differs — one mismatch is enough to answer false.

How to solve Univalued Binary Tree

The only candidate for the common value is the root's value, so the question becomes: does any node differ from the root?

Approach

  1. Remember v = root.val.
  2. Traverse the tree (depth-first with a stack, or breadth-first with a queue).
  3. If a node's value is not v, return false immediately.
  4. If the traversal finishes, return true.

Complexity

  • Time — O(n)
  • Space — O(h) for a depth-first stack

Pitfalls

  • Comparing each node only with its parent also works, but comparing everything with one fixed value is simpler and just as fast.

Reference solution

Python

from typing import Optional

def isUnivalTree(root: Optional[TreeNode]) -> bool:
    v = root.val
    stack = [root]
    while stack:
        node = stack.pop()
        if node.val != v:
            return False
        if node.left:
            stack.append(node.left)
        if node.right:
            stack.append(node.right)
    return True

Java

public static boolean isUnivalTree(TreeNode root) {
    return same(root, root.val);
}

static boolean same(TreeNode node, int v) {
    if (node == null) return true;
    return node.val == v && same(node.left, v) && same(node.right, v);
}

C++

bool sameValue(TreeNode* node, int v);

bool isUnivalTree(TreeNode* root) {
    return sameValue(root, root->val);
}

bool sameValue(TreeNode* node, int v) {
    if (!node) return true;
    return node->val == v && sameValue(node->left, v) && sameValue(node->right, v);
}

JavaScript

var isUnivalTree = function(root) {
    var v = root.val, stack = [root];
    while (stack.length > 0) {
        var node = stack.pop();
        if (node.val !== v) return false;
        if (node.left !== null) stack.push(node.left);
        if (node.right !== null) stack.push(node.right);
    }
    return true;
};

Also on the editorial tab: C, C#, Go, Kotlin, PHP, Ruby, Rust, Swift, TypeScript.

All 201 depth-first search problems · the whole catalogue

Learn the technique: Depth-First Search (DFS) · Breadth-First Search (BFS)