Univalued Binary Tree

Univalued Binary Tree

What is this problem about?

The Univalued Binary Tree interview question is a straightforward but important tree problem. A binary tree is "univalued" if every node in the tree has the same value. Your task is to write a function that takes the root of a binary tree and returns true if it is univalued and false otherwise.

Why is this asked in interviews?

Companies like Google and Twilio use the Univalued Binary Tree coding problem to verify a candidate's basic understanding of tree traversals. It’s an ideal problem for seeing if a candidate can write clean recursive code and handle edge cases like empty trees or trees with only a single node.

Algorithmic pattern used

The primary Breadth-First Search, Depth-First Search, Binary Tree, Tree interview pattern here is simple recursion (DFS). You compare the value of the current node with its left child (if it exists) and its right child (if it exists). If they are different, you immediately return false. If they are the same, you recursively check the left and right subtrees. Alternatively, you can pass the value of the root node down through the recursion and ensure every node matches that initial value.

Example explanation

Consider a tree where the root is 5, and both children are 5.

1. Root is 5.
2. Left child is 5. (Matches root).
3. Right child is 5. (Matches root).
4. Recursively check children of children. If all are 5, return true. Now consider a tree where the root is 1, children are 1, but one leaf node is 2.
5. Root is 1.
6. Traverse until the leaf 2.
7. 2 does not match the root value 1.
8. Return false.

Common mistakes candidates make

The most common mistake is not checking for null children before accessing their values, which leads to a null pointer exception. Another error is overcomplicating the logic with global variables when a simple boolean return in recursion is sufficient. Finally, forgetting that an empty tree is usually considered univalued (though this depends on the specific definition given).

Interview preparation tip

Master the Recursive Tree Traversal pattern. Almost all tree problems involve visiting every node and performing a check. If you can write a clean DFS, you can solve a significant percentage of entry-level tree questions.