Tree Coloring - Amazon Top Interview Questions


Problem Statement :


You are given a binary tree root where the value of each node represents its color. In the tree there are at most 2 colors. Return whether it's possible to swap the colors of the nodes any number of times so that no two adjacent nodes have the same color.

Constraints

n ≤ 100,000 where n is the number of nodes in root

Example 1

Input

root = [1, [1, null, null], [1, [0, null, [0, null, null]], [0, null, null]]]

Output

True

Explanation

We can color the root with 0, the next level 1s, third level 0s and fourth level 1s

Example 2

Input

root = [5, null, [9, [5, null, null], [9, null, null]]]

Output

False

There's no way to color the nodes so that no two adjacent nodes have the same color.


Solution :



title-img 




                        Solution in C++ :

/**
 * class Tree {
 *     public:
 *         int val;
 *         Tree *left;
 *         Tree *right;
 * };
 */

int dfs(Tree *root, int color) {
    if (!root) return 0;
    return color + dfs(root->left, 1 - color) + dfs(root->right, 1 - color);
}

void countNodes(Tree *root, int firstColor, int &firstCount, int &secondCount) {
    if (!root) return;

    if (root->val == firstColor)
        ++firstCount;
    else
        ++secondCount;

    countNodes(root->left, firstColor, firstCount, secondCount);
    countNodes(root->right, firstColor, firstCount, secondCount);
}

bool solve(Tree *root) {
    if (!root) return true;

    int req = dfs(root, 1), firstColor = root->val, firstCount = 0, secondCount = 0;
    countNodes(root, firstColor, firstCount, secondCount);
    return req == firstCount || req == secondCount;
}
                    




                        Solution in Python : 
                            
# class Tree:
#     def __init__(self, val, left=None, right=None):
#         self.val = val
#         self.left = left
#         self.right = right
class Solution:
    def solve(self, root):
        if not root:
            return True
        evens = 0  # how many nodes are in even layers
        tot = 0  # how many total nodes there are
        firstCnt = 0  # how many nodes have the "first" color
        first = root.val  # we assign the root node's color to be the first color
        q = collections.deque([(root, 0)])
        while q:
            curr, lvl = q.popleft()
            tot += 1
            if curr.val == first:
                firstCnt += 1
            if lvl % 2:
                evens += 1
            if curr.left:
                q.append((curr.left, lvl + 1))
            if curr.right:
                q.append((curr.right, lvl + 1))
        return evens in [
            firstCnt,
            tot - firstCnt,
        ]  # the even layers can get the first or second color


View More Similar Problems

Minimum Average Waiting Time

Tieu owns a pizza restaurant and he manages it in his own way. While in a normal restaurant, a customer is served by following the first-come, first-served rule, Tieu simply minimizes the average waiting time of his customers. So he gets to decide who is served first, regardless of how sooner or later a person comes. Different kinds of pizzas take different amounts of time to cook. Also, once h

View Solution →

Merging Communities

People connect with each other in a social network. A connection between Person I and Person J is represented as . When two persons belonging to different communities connect, the net effect is the merger of both communities which I and J belongs to. At the beginning, there are N people representing N communities. Suppose person 1 and 2 connected and later 2 and 3 connected, then ,1 , 2 and 3 w

View Solution →

Components in a graph

There are 2 * N nodes in an undirected graph, and a number of edges connecting some nodes. In each edge, the first value will be between 1 and N, inclusive. The second node will be between N + 1 and , 2 * N inclusive. Given a list of edges, determine the size of the smallest and largest connected components that have or more nodes. A node can have any number of connections. The highest node valu

View Solution →

Kundu and Tree

Kundu is true tree lover. Tree is a connected graph having N vertices and N-1 edges. Today when he got a tree, he colored each edge with one of either red(r) or black(b) color. He is interested in knowing how many triplets(a,b,c) of vertices are there , such that, there is atleast one edge having red color on all the three paths i.e. from vertex a to b, vertex b to c and vertex c to a . Note that

View Solution →

Super Maximum Cost Queries

Victoria has a tree, T , consisting of N nodes numbered from 1 to N. Each edge from node Ui to Vi in tree T has an integer weight, Wi. Let's define the cost, C, of a path from some node X to some other node Y as the maximum weight ( W ) for any edge in the unique path from node X to Y node . Victoria wants your help processing Q queries on tree T, where each query contains 2 integers, L and

View Solution →

Contacts

We're going to make our own Contacts application! The application must perform two types of operations: 1 . add name, where name is a string denoting a contact name. This must store name as a new contact in the application. find partial, where partial is a string denoting a partial name to search the application for. It must count the number of contacts starting partial with and print the co

View Solution →