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

How we wrote xtensor 8/N: iterators

Python vs NodeJs: Which one should you go for in 2022?

My Journey From Open Source Noob to Google Summer of Code 2020

AI LEARNS TO PLAY FLAPPY BIRD GAME — FUN PROJECT — WITH SOURCE CODE

AI plays Flappy bird game

Deploy SpringBoot Project On Ubuntu Server at DigitalOcean.

Makers Apprenticeship — Week 1

Overview of Salesforce lightning components

How to Setup SpamAssassin With Postfix On Ubuntu 16.04

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

Cross the Bridge Puzzle

Leetcode 862. Shortest Subarray with Sum at Least K

PlatinumX Tech’s Algorithm Expert Course Review (How I got into Turing).

LeetCode 242 — Valid Anagram