Univalued Binary Tree - Leetcode

Leetcode Solution: Understand and solve Leetcode problem Univalued Binary Tree(965)

25 August 2020

In this article we’ll be solving the problem: Univalued Binary Tree. This problem belongs to Tree Traversal category and just like the problem, Maximum Depth of N Ary Tree and Increasing Order Search Tree this problem also requires a slight modification in a simple Tree Traversal approach.

		
				
A binary tree is univalued if every node in the tree has the same value.

Return true if and only if the given tree is univalued.
Example 1:
    Input: [1,1,1,1,1,null,1]
    Output: true

Example 2:
    Input: [2,2,2,5,2]
    Output: false

Note:
    The number of nodes in the given tree will be in the range [1, 100].
    Each node's value will be an integer in the range [0, 99].

In this problem we’ve to check if all the nodes have the same value or not. This problem belongs to the Tree traversal category. Here we’ve to update the tree traversal logic by including the value comparison for all the nodes that are getting traversed.

As, all the nodes are supposed to have the same value, I’ll be using the root node’s value to compare with other nodes. For this I’ll create a variable, rootValue, to store the value for the root node.

var rootValue int
rootValue = root.Val

Here’s the modified pre order approach:

func preOrder(root *TreeNode) bool {
    if root.Val != rootValue {
        return false
    }
    leftStatus := true
    if root.Left != nil {
        leftStatus = preOrder(root.Left)
    }
    rightStatus := true
    if root.Right != nil {
        rightStatus = preOrder(root.Right)
    }
    return leftStatus && rightStatus
}

The modifications, in the simple preOrder approach, that I’ve done here is:

I’m comparing the current node’s value with the rootValue variable that we’ve created.
If the values do not match then I do not continue the traversal and return false
If the values match then
- I call the preOrder for the left child, and the right child
- Check if their values did match or not

Here’s the complete solution:

var rootValue int

func isUnivalTree(root *TreeNode) bool {
    if root == nil {
        return false
    }
    rootValue = root.Val
    return preOrder(root)
}

func preOrder(root *TreeNode) bool {
    if root.Val != rootValue {
        return false
    }
    leftStatus := true
    if root.Left != nil {
        leftStatus = preOrder(root.Left)
    }
    rightStatus := true
    if root.Right != nil {
        rightStatus = preOrder(root.Right)
    }
    return leftStatus && rightStatus
}

The code can be found here on GitHub as well.

Loading Comments... Disqus Loader

Univalued Binary Tree - Leetcode

Leetcode Solution: Understand and solve Leetcode problem Univalued Binary Tree(965)

Related Pages: