965. Univalued Binary Tree

EasyTreeDepth-First SearchBreadth-First SearchBinary Tree
Leetcode Link

Problem Description

The goal is to determine whether all the nodes in a binary tree have the same value. In other words, we are given the root node of a binary tree and need to check if every node in the tree has the same value as the root, which would make it a uni-valued binary tree. The function should return true if the tree is uni-valued, otherwise, it should return false. A binary tree is a data structure in which each node has at most two children, referred to as the left child and the right child.

Intuition

To check if a binary tree is uni-valued, one effective approach is to perform a Depth-First Search (DFS) starting from the root of the tree. During the DFS, we compare the value of each node we visit to the value of the root node. If at any point we find a node that has a different value than the root, we can conclude that the tree is not uni-valued and immediately return false. If the search completes without finding any differing value, then the tree is uni-valued and we return true.

In the provided solution, a recursive dfs function is defined which carries out the above logic. It checks if the current node (node) is None, signifying the end of a branch, and returns true in that case, since a non-existent node does not contradict the uni-valued property. If the node exists, the function checks whether its value matches the root's value and also recursively calls itself on the node's left and right children. The main function isUnivalTree initiates the DFS by calling dfs function on the root. If all nodes are consistent with the root's value, the dfs function will return true; otherwise, it will return false at some point during the recursion.

Learn more about Tree, Depth-First Search, Breadth-First Search and Binary Tree patterns.

Not Sure What to Study? Take the 2-min Quiz to Find Your Missing Piece๏ผš

Which of the following is a good use case for backtracking?

Solution Approach

The implementation of the solution involves a depth-first search (DFS) algorithm applied to a binary tree data structure. The DFS algorithm is a recursive strategy used to traverse all the nodes in a tree starting from some node (usually the root) and explores as far down the branches as possible before backtracking.

The core function dfs in the solution uses recursion to travel through the tree. At each node, it performs the following steps:

  1. It checks if the current node is None. If yes, it returns true, indicating the end of this branch is reached without finding any contradicting node.

  2. If the current node is not None, it compares the value of the current node (node.val) with the value of the root node (root.val):

    • If node.val is equal to root.val, the node matches the required condition for a uni-valued tree. The function then proceeds with the recursion and calls dfs(node.left) and dfs(node.right). Both these calls must return true to confirm that both the left and right subtrees are also uni-valued.

    • If node.val is not equal to root.val, the function immediately returns false, indicating the tree is not uni-valued.

  3. The result of the dfs function relies on the logical AND && operator between the comparison check and the recursive calls. This ensures that every node must satisfy the condition to return true for the overall result to be true.

When isUnivalTree is called with the root of the tree, it starts the dfs algorithm by calling the dfs function for the first time. If the entire tree is explored without finding any differing values, the function will ultimately return true. Otherwise, the discovery of any node that does not match the root's value will result in an early termination of the dfs function with a false result.

Discover Your Strengths and Weaknesses: Take Our 2-Minute Quiz to Tailor Your Study Plan:

What is the best way of checking if an element exists in an unsorted array once in terms of time complexity? Select the best that applies.

Example Walkthrough

Let's consider a small binary tree as an example to illustrate the solution approach:

1    1
2   / \
3  1   1
4 / \
51   1

In this binary tree, we have the root node with a value of 1, and all child nodes also have the value 1. We will apply the dfs algorithm to determine if this is a uni-valued binary tree.

We begin by calling the isUnivalTree function with the root node:

  1. The dfs function is called with the root node (value 1). Since the node is not None and its value matches the root's value, the function proceeds to check its children.

  2. The dfs function is then recursively called on the left child of the root (value 1). Again, this node is not None, and its value matches the root's value. So we move on to its children:

    • The recursive call to its left child (value 1) returns true as there are no more children to check and it matches the root's value.
    • The recursive call to its right child (value 1) also returns true for the same reason.

  3. Since both recursive calls for the left child of the root returned true, the dfs function progresses to the right child of the root.

  4. The right child of the root (value 1) is not None and its value does match the root's value. Since it has no children, the recursive calls on its left and right will both return true.

  5. At this point, all nodes have been checked, and they all have the same value as the root node. Therefore, every dfs call has returned true, making the binary tree uni-valued.

Finally, isUnivalTree receives a true result from the dfs function, indicating that the tree is indeed uni-valued. We can conclude that given the structure and values, the example binary tree is uni-valued and our function will correctly return true.

Solution Implementation

1# Definition for a binary tree node.
2class TreeNode:
3    def __init__(self, val=0, left=None, right=None):
4        self.val = val  # Value of the node
5        self.left = left  # Reference to the left child
6        self.right = right  # Reference to the right child
7
8class Solution:
9    def isUnivalTree(self, root: TreeNode) -> bool:
10        """
11        Determines if a tree is a unival tree (where all nodes have the same value)
12      
13        Args:
14        root: The root of the binary tree.
15      
16        Returns:
17        A boolean value indicating if the tree is a unival tree.
18        """
19
20        # Helper function to perform depth-first search
21        def depth_first_search(node):
22            # If we reach a None, it means we are at a leaf node, or the tree is empty
23            # Since a None is technically univalued, we return True here
24            if node is None:
25                return True
26          
27            # Check if the current node's value is same as the root's value
28            # And recursively check the left and right subtrees
29            return (node.val == root.val 
30                    and depth_first_search(node.left) 
31                    and depth_first_search(node.right))
32
33        # Start the depth-first search from the root
34        return depth_first_search(root)
35
1/**
2 * Definition for a binary tree node.
3 */
4public class TreeNode {
5    int val; // Value of the node
6    TreeNode left; // Left child
7    TreeNode right; // Right child
8    TreeNode() {} // Constructor without parameters
9    TreeNode(int val) { this.val = val; } // Constructor with value parameter
10    // Constructor with value and left, right children parameters
11    TreeNode(int val, TreeNode left, TreeNode right) {
12        this.val = val;
13        this.left = left;
14        this.right = right;
15    }
16}
17
18class Solution {
19    // Public method to check if a tree is a univalued tree
20    public boolean isUnivalTree(TreeNode root) {
21        // If the root is null, the tree is trivially univalued
22        if (root == null) {
23            return true;
24        }
25        // Use depth-first search starting with the root value to check univalued property
26        return dfs(root, root.val);
27    }
28
29    // Private helper method to perform depth-first search on tree nodes
30    private boolean dfs(TreeNode node, int val) {
31        // If the current node is null, we've reached the end of a branch - return true
32        if (node == null) {
33            return true;
34        }
35        // Check if the current node value is equal to the given value
36        // and recursively check both the left and right subtrees
37        return node.val == val && dfs(node.left, val) && dfs(node.right, val);
38    }
39}
40
1// Definition for a binary tree node.
2struct TreeNode {
3    int val;
4    TreeNode *left;
5    TreeNode *right;
6    // Constructor to initialize node with a value, and with left and right child pointers set to nullptr.
7    TreeNode(int x) : val(x), left(nullptr), right(nullptr) {}
8    // Constructor to initialize node with a value and explicit left and right child nodes.
9    TreeNode(int x, TreeNode *left, TreeNode *right) : val(x), left(left), right(right) {}
10};
11
12class Solution {
13public:
14    // Public method to check if a tree is a unival tree, where all nodes' values are the same.
15    bool isUnivalTree(TreeNode* root) {
16        // Call the private DFS method, starting with the root's value, to check for unival.
17        return dfs(root, root->val);
18    }
19
20private:
21    // Private helper method to perform DFS and check if all nodes' values are equal to a given value.
22    bool dfs(TreeNode* node, int val) {
23        // If the current node is nullptr, return true because we have not encountered a different value.
24        if (!node) return true;
25      
26        // Check if the current node's value equals the given value and 
27        // recursively call DFS for both left and right subtrees.
28        // The tree is unival down the current path only if both subtrees are also unival.
29        return node->val == val && dfs(node->left, val) && dfs(node->right, val);
30    }
31};
32
1// To check if a binary tree is a unival tree (all nodes have the same value)
2
3// Function to check if the tree is a unival tree
4function isUnivalTree(root: TreeNode | null): boolean {
5    if (!root) {
6        return true; // An empty tree is considered a unival tree
7    }
8
9    // Helper function to perform depth-first search
10    function checkUnival(root: TreeNode | null, value: number): boolean {
11        if (root === null) {
12            return true; // Reached the end of a branch
13        }
14        if (root.val !== value) {
15            return false; // Current node value doesn't match the value we're checking against
16        }
17        // Recursively check left and right subtrees
18        return checkUnival(root.left, value) && checkUnival(root.right, value);
19    }
20
21    // Start checking univality from the root node using its value
22    return checkUnival(root, root.val);
23}
24
25// Definition for a binary tree node
26class TreeNode {
27    val: number;
28    left: TreeNode | null;
29    right: TreeNode | null;
30
31    constructor(val?: number, left?: TreeNode | null, right?: TreeNode | null) {
32        this.val = val === undefined ? 0 : val;
33        this.left = left === undefined ? null : left;
34        this.right = right === undefined ? null : right;
35    }
36}
37
38// Example usage:
39// const tree = new TreeNode(1, new TreeNode(1), new TreeNode(1));
40// console.log(isUnivalTree(tree)); // Output: true
41
Not Sure What to Study? Take the 2-min Quiz๏ผš

What is the running time of the following code?

1int sqrt(int n) {
2  for (int guess = 1; guess * guess <= n; guess++) {
3    if (guess * guess == n) {
4      return guess;
5    }
6  }
7  return -1;
8}

Time and Space Complexity

Time Complexity

The time complexity of the provided code is O(n), where n is the number of nodes in the binary tree. This is because each node in the tree is visited exactly once to check whether it matches the value of the root node.

Space Complexity

The space complexity of the code is O(h), where h is the height of the binary tree. This is the space required by the call stack due to recursion. In the worst case, where the tree is skewed, the space complexity would be O(n), corresponding to the number of recursive calls equal to the number of nodes in a skewed tree.

Learn more about how to find time and space complexity quickly using problem constraints.

Fast Track Your Learning with Our Quick Skills Quiz:

A person thinks of a number between 1 and 1000. You may ask any number questions to them, provided that the question can be answered with either "yes" or "no".

What is the minimum number of questions you needed to ask so that you are guaranteed to know the number that the person is thinking?

Recommended Readings

Everything About Trees

Everything About Trees A tree is a type of graph data structure composed of nodes and edges Its main properties are It is acyclic doesn't contain any cycles There exists a path from the root to any node Has N 1 edges where N is the number of nodes in the tree and

DFS Fundamentals

https algomonster s3 us east 2 amazonaws com cover_photos dfs svg Depth First Search Prereqs Recursion Review problems recursion_intro Trees problems tree_intro With a solid understanding of recursion under our belts we are now ready to tackle one of the most useful techniques in coding interviews Depth First Search DFS

BFS Fundamentals

https algomonster s3 us east 2 amazonaws com cover_photos bfs svg Breadth First Search on Trees Hopefully by this time you've drunk enough DFS Kool Aid to understand its immense power and seen enough visualization to create a call stack in your mind Now let me introduce the companion spell

Got a question?ย Ask the Teaching Assistantย anything you don't understand.

Still not clear? Ask in the Forum, ย Discordย orย Submitย the part you don't understand to our editors.

โ†
โ†‘TA ๐Ÿ‘จโ€๐Ÿซ