Leetcode – Univalued Binary Tree Solution in Python

Spread the love

Binary trees are a fundamental data structure in computer science, and they provide a host of intriguing problems to solve, helping to hone one’s algorithmic skills. One such problem is the “Univalued Binary Tree” on Leetcode. In this exhaustive article, we’ll unravel the problem, understand its intricacies, and formulate a Python-based solution.

Problem Statement

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

Understanding the Problem

A univalued binary tree implies that as we traverse the tree, each node we encounter should have the same value. This immediately points us to a depth-first search (DFS) or breadth-first search (BFS) traversal strategy. If at any point we find a node with a different value, we can immediately conclude that the tree is not univalued.

Key Insight

We don’t need to check all nodes with all other nodes. We just need to ensure each node’s value is consistent with its parent. This can considerably simplify the traversal logic.

Algorithm to Solve the Problem

Using a depth-first search (DFS) approach:

  1. Start with the root of the tree.
  2. For every node encountered:
    • Compare the node’s value with the root’s value.
    • If they differ, return false.
    • Otherwise, continue the DFS traversal for its children.
  3. If the entire tree is traversed without discrepancies, return true.

Python Code Solution

To implement the solution, let’s define the structure for the binary tree node:

class TreeNode:
    def __init__(self, val=0, left=None, right=None):
        self.val = val
        self.left = left
        self.right = right

Now, let’s write the function to check if the tree is univalued:

def isUnivalTree(root):
    if not root:
        return True

    if root.left and root.left.val != root.val:
        return False
    if root.right and root.right.val != root.val:
        return False

    return isUnivalTree(root.left) and isUnivalTree(root.right)

Complexity Analysis

  • Time Complexity: O(N) – We essentially perform a DFS traversal, visiting each node once.
  • Space Complexity: O(H) – Where H is the height of the tree. This accounts for the space used by the call stack during the recursive DFS traversal. In the worst case, when the tree is skewed, the space complexity can be O(N).

Testing the Solution

It’s crucial to verify the solution across various test cases:

# Create a sample univalued binary tree: 1 -> 1 -> 1
tree1 = TreeNode(1)
tree1.left = TreeNode(1)
tree1.right = TreeNode(1)

# Create a sample non-univalued binary tree: 1 -> 1 -> 2
tree2 = TreeNode(1)
tree2.left = TreeNode(1)
tree2.right = TreeNode(2)

print(isUnivalTree(tree1))  # Expected output: True
print(isUnivalTree(tree2))  # Expected output: False

Alternative Approach: Using BFS

Another intuitive way to tackle this problem is by using BFS, where you traverse the tree level by level. This involves using a queue to store nodes for checking:

def isUnivalTree(root):
    if not root:
        return True

    queue = [root]
    val = root.val

    while queue:
        current = queue.pop(0)
        if current.val != val:
            return False
        if current.left:
            queue.append(current.left)
        if current.right:
            queue.append(current.right)

    return True

Conclusion

The “Univalued Binary Tree” problem, while seemingly simple, offers a profound insight into tree traversal techniques and the importance of algorithmic optimization. Through problems like this, Leetcode encourages coders to think critically, weighing the pros and cons of DFS vs. BFS and considering edge cases.

Leave a Reply