Univalued Binary Tree

easy binary tree dfs recursion

Problem

A binary tree is univalued if every node in the tree has the same value. Given the root of a binary tree, return true if the tree is univalued, otherwise return false.

Inputroot = [1, 1, 1, 1, 1, null, 1]

Outputtrue

Every reachable node holds the value 1, so the tree is univalued.

tree (level-order, comma-separated, use null)

def is_unival_tree(root):
    val = root.val
    def dfs(node):
        if node is None:
            return True
        if node.val != val:
            return False
        return dfs(node.left) and dfs(node.right)
    return dfs(root)

function isUnivalTree(root) {
  const val = root.val;
  function dfs(node) {
    if (node === null) return true;
    if (node.val !== val) return false;
    return dfs(node.left) && dfs(node.right);
  }
  return dfs(root);
}

class Solution {
    public boolean isUnivalTree(TreeNode root) {
        return dfs(root, root.val);
    }
    private boolean dfs(TreeNode node, int val) {
        if (node == null) return true;
        if (node.val != val) return false;
        return dfs(node.left, val) && dfs(node.right, val);
    }
}

class Solution {
public:
    bool isUnivalTree(TreeNode* root) {
        return dfs(root, root->val);
    }
    bool dfs(TreeNode* node, int val) {
        if (node == nullptr) return true;
        if (node->val != val) return false;
        return dfs(node->left, val) && dfs(node->right, val);
    }
};

Explanation

A tree is univalued when every node holds the same value. The simplest plan is to pick the root's value as the reference and make sure no node disagrees with it.

We grab val = root.val once, then a recursive dfs(node) walks the whole tree. An empty spot is fine (returns True). If a node's value differs from val, we immediately return False.

Otherwise the node is good so far, and the tree is univalued only if both subtrees are too — that is the dfs(node.left) and dfs(node.right). A single mismatch anywhere makes the answer false.

Example: [1,1,1,1,1,null,1]. The reference value is 1, and every reachable node also holds 1, so every check passes and the result is true.

We look at each node once, giving O(n) time.

Time: O(n) Space: O(h)