Univalued Binary Tree

We want to determine if a given binary tree is uni-valued, meaning that all nodes in the tree have the same value.

Approach

1. Define a Recursive Function: A simple way to solve this problem is by using a recursive function that traverses the tree and checks if all the nodes have the same value.

2. Check Node Values: In the recursive function, check if the current node’s value is the same as its parent’s value. If not, the tree is not uni-valued.

3. Traverse Left and Right Subtrees: Continue to traverse the left and right subtrees of the current node, performing the same check at each level.

4. Base Case: If the current node is None, return True as there are no values to compare in this branch.

5. Final Result: The tree is uni-valued if all recursive calls return True.

Code

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12

class Solution:
    def isUnivalTree(self, root: Optional[TreeNode]) -> bool:
        # Define a recursive function to check if the subtree rooted at node has the same value as val
        def isUniVal(node, val):
            if node is None:
                return True
            if node.val != val:
                return False
            return isUniVal(node.left, val) and isUniVal(node.right, val)

        # Start the recursion from the root with the value of the root
        return isUniVal(root, root.val)

Example

• Input: root = [1,1,1,1,1,null,1]
• Output: true
• Explanation: All nodes have the value 1, so the tree is uni-valued.

Insights

• Time Complexity: The time complexity of this solution is (O(n)), where (n) is the number of nodes in the tree. We visit each node exactly once.

• Space Complexity: The space complexity is (O(h)), where (h) is the height of the tree. This is the maximum amount of space required by the recursion stack.

• Simple Recursive Solution: The solution demonstrates a simple use of recursion to traverse a binary tree and perform a comparison at each node.

  1. We have to visit all nodes
  2. It does not matter which traversal you use
  3. When you encounter a different value immediately return false
  4. Search for invariant
     • Definition of the term univalued

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35

# Definition for a binary tree node.
# class TreeNode
#     attr_accessor :val, :left, :right
#     def initialize(val = 0, left = nil, right = nil)
#         @val = val
#         @left = left
#         @right = right
#     end
# end
# @param {TreeNode} root
# @return {Boolean}

def wrapper(root, unival)
    if root.nil?
        return true
    end

    if root.left and root.left.val != unival
        return false
    end
    if root.right and root.right.val != unival
        return false
    end

    left = wrapper(root.left, unival) 
    right = wrapper(root.right, unival)

    left and right
end

def is_unival_tree(root)
    unival = root.val

    wrapper(root, unival)    
end