1. Introduction

A binary tree is uni-valued if every node in the tree has the same value. 

Given the root of a binary tree, return true if the tree is uni-valued, or false otherwise.

2. Content

In this article, we will discuss two different ways to solve the Leetcode 965 question. Univalued Binary Trees are those trees that have one value in all of its nodes. If all nodes have the same value, then return true, else return false.

Example 1

Example 2

3. Using Inorder traversal

We can do inorder traversal or any tree traversal and store data in some data structure. Then we check if all elements are the same or not. If yes, we return true, false otherwise.

    public boolean isUnivalTreeInorder(TreeNode root) {
        if(root == null) return true;
        List<Integer> result = inorderRecursive(root);
        int val = result.get(0);
        for (Integer elem : result) {
            if(elem != val) return false;
        }
        return true;
    }

    public List<Integer> inorderRecursive(TreeNode root) {
        List<Integer> result = new ArrayList<>();
        inorderRecursive(root, result);
        return Collections.unmodifiableList(result);
    }

    private void inorderRecursive(TreeNode root, List<Integer> result) {
        if(root != null) {
            inorderRecursive(root.left, result);
            result.add(root.val);
            inorderRecursive(root.right, result);
        }
    }

Time Complexity:

1. O(n) where n is the total number of nodes in the tree. We need to traverse the entire tree to check if the tree is univalued.

Space complexity:

1. O(n) where n is the total number of nodes in the tree as we are saving all elements of the tree in an ArrayList.

4. Using plain DFS/recursion

With plain DFS, we don’t store all the node values. We just need the root’s value and compare that with another node’s value. This way we don’t need to save all the values of nodes in any data structure, hence saving auxiliary space. With this solution, we will just use system stack space.

    public boolean isUnivalTree(Tree.TreeNode root) {
        return isUnivalTree(root, root.val);
    }

    boolean isUnivalTree(Tree.TreeNode root, int val) {
        if (root == null) return true;
        if (root.val != val) return false;
        return isUnivalTree(root.left, val) && isUnivalTree(root.right, val);
    }

Time Complexity:

1. O(n) where n is the total number of nodes in the tree. We need to traverse the entire tree to check if the tree is univalued.

Space complexity:

1. O(h) where h is the height of the tree. If the tree is skewed, then the space complexity will be O(n).

5. Using BFS/Iteration(Queue)

We can solve this problem using BFS too. We just need an auxiliary data structure to save the nodes that we are traversing at the current level.

public boolean isUnivalTreeUsingQueue(TreeNode root) {
    if (root == null) return true;

    Deque<TreeNode> queue = new ArrayDeque<>();
    queue.add(root);
    int val = root.val;

    while (!queue.isEmpty()) {
        TreeNode curr = queue.poll();
        if (curr.val != val) return false;
        if (curr.left != null) queue.add(curr.left);
        if (curr.right != null) queue.add(curr.right);
    }

    return true;
}

Time Complexity:

1. O(n) where n is the total number of nodes in the tree. We need to traverse the entire tree to check if the tree is univalued.

Space complexity:

1. O(W) or O(N) where W width of tree i.e. highest nodes at any level. We can also say that it is O(N) as we will save all nodes in the Queue.

6. Conclusion

In this article we saw 2 different ways to solve the question Univalued Binary Tree.

GitHub Link: https://github.com/savanibharat/justamonad-tutorials/blob/master/justamonad-tutorials-leetcode/src/main/java/com/justamonad/tutorials/leetcode/tree/UnivaluedTree.java