965. Univalued Binary Tree

EasyTreeDepth-First SearchBreadth-First SearchBinary Tree

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.

Flowchart Walkthrough

Let's analyze Leetcode 965. Univalued Binary Tree using the Flowchart. Here's a detailed breakdown based on the decision flow:

Is it a graph?
- Yes: A binary tree is a type of graph.
Is it a tree?
- Yes: A binary tree is definitively a tree structure.
Is the problem related to directed acyclic graphs (DAGs)?
- No: While a binary tree is directed and acyclic, the specific problem isn't about processing DAG properties like topological sorting.
Is the problem related to shortest paths?
- No: The problem is about verifying whether all nodes contain the same value, not about finding paths.
Does the problem involve connectivity?
- No: The objective isn't to determine connectivity or components but to check a uniform property across all nodes.

From the flowchart analysis:

The tree node connects directly to the use of DFS since the problem involves processing information across potentially all nodes in a structured manner (the tree) to verify a single, consistent value.

Conclusion: According to the flowchart, the use of Depth-First Search (DFS) is appropriate for this problem since it efficiently allows checking each node to ensure all values in the binary tree are uniform.

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.

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:

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.
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.
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.

Ready to land your dream job?

Unlock your dream job with a 2-minute evaluator for a personalized learning plan!

Start Evaluator

Example Walkthrough

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

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:

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.
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.
Since both recursive calls for the left child of the root returned true, the dfs function progresses to the right child of the root.
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.
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

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.

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

Question 1 out of 10

What does the following code do?

1def f(arr1, arr2):
2  i, j = 0, 0
3  new_arr = []
4  while i < len(arr1) and j < len(arr2):
5      if arr1[i] < arr2[j]:
6          new_arr.append(arr1[i])
7          i += 1
8      else:
9          new_arr.append(arr2[j])
10          j += 1
11  new_arr.extend(arr1[i:])
12  new_arr.extend(arr2[j:])
13  return new_arr
14

1public static List<Integer> f(int[] arr1, int[] arr2) {
2  int i = 0, j = 0;
3  List<Integer> newArr = new ArrayList<>();
4
5  while (i < arr1.length && j < arr2.length) {
6      if (arr1[i] < arr2[j]) {
7          newArr.add(arr1[i]);
8          i++;
9      } else {
10          newArr.add(arr2[j]);
11          j++;
12      }
13  }
14
15  while (i < arr1.length) {
16      newArr.add(arr1[i]);
17      i++;
18  }
19
20  while (j < arr2.length) {
21      newArr.add(arr2[j]);
22      j++;
23  }
24
25  return newArr;
26}
27

1function f(arr1, arr2) {
2  let i = 0, j = 0;
3  let newArr = [];
4  
5  while (i < arr1.length && j < arr2.length) {
6      if (arr1[i] < arr2[j]) {
7          newArr.push(arr1[i]);
8          i++;
9      } else {
10          newArr.push(arr2[j]);
11          j++;
12      }
13  }
14  
15  while (i < arr1.length) {
16      newArr.push(arr1[i]);
17      i++;
18  }
19  
20  while (j < arr2.length) {
21      newArr.push(arr2[j]);
22      j++;
23  }
24  
25  return newArr;
26}
27

Find the intersection of two arrays.

Check if one array is a subsequence of the other.

Merge two sorted arrays.

Finding median values of 2 arrays.

I don’t know