Unival Trees — Asked in Google and Amazon Interview

Problem Statement :

You are given a binary tree. Return the count of unival sub-trees in the given binary tree. In unival trees, all the nodes, below the root node, have the same value as the data of the root.

The input consists of values of nodes separated by a single space in a single line. In case a node is null, we take -1 on its place.

Sample Input:

1 2 3 2 -1 3 4 -1 -1 3 3 -1 -1 -1 -1 -1 -1

Sample Output:

6

Approach :

Bottom-Up Approach

In this approach, we will count the number of unival subtrees in a bottom-up manner. This means we will calculate the count of unival subtrees from left and right subtrees and also calculate whether they are themselves unival or not. Now for each node to be visited, the tree with root as the current node is unival if and only if both the left and right subtree is unival and the values of left and right child(if exists) should also be equal to the value of the current node. So if these conditions are satisfied we will increment the total count and return this value and a true boolean value to denote the count of unival nodes and that the current node is also unival. Otherwise, we will return the total count(without incrementing) with a false boolean value denoting that the given current subtree is not unival.

Time Complexity : O(N)
Space Complexity : O(N)

Code :

Thanks for Reading

Placewit grows the best engineers by providing an interactive classroom experience and by helping them develop their skills and get placed in amazing companies.

Learn more at Placewit. Follow us on Instagram and Facebook for daily learning.

--

--

--

Upskilling students for tech placements!

Love podcasts or audiobooks? Learn on the go with our new app.

Recommended from Medium

Day 18 RayCast learned

Refactoring untamed code horses from the other world

Django Template Integration

SAP ABAP for Beginners

I’m Learning to Use Flatbuffer in Go (Golang) , Here What I Learn

07/20/2021 FEC Day 1

DREP Monthly Report 6.1–6.30|DREP’s

Cleaning datasets with Python

Get the Medium app

A button that says 'Download on the App Store', and if clicked it will lead you to the iOS App store
A button that says 'Get it on, Google Play', and if clicked it will lead you to the Google Play store
Placewit

Placewit

Upskilling students for tech placements!

More from Medium

Longest Increasing Subsequence Coding Question

543. Diameter of Binary Tree

LeetCode 146. LRU Cache

Leetcode 701. Insert into a Binary Search Tree