Coding Week 8 - Binary Tree

Question 1

Problem 1) Cousins in Binary Tree

Given the root of a binary tree with unique values and the values of two different nodes of the tree x and y, return true if the nodes corresponding to the values x and y in the tree are cousins, or false otherwise.

Two nodes of a binary tree are cousins if they have the same depth with different parents.

Note that in a binary tree, the root node is at the depth 0, and children of each depth k node are at the depth k + 1.

Example 1:

Input: root = [1,2,3,4], x = 4, y = 3
Output: false

Question 1) Consider the tree in example 1. Suppose your node 4, then what is your relation with node 3?

A) Node 3 is your cousin
B) Node 3 is your parent
C) Node 3 is your uncle
D) Node 3 is your grandparent

Answer 1

C) Node 3 is your uncle

Question 2

Problem 1) Cousins in Binary Tree

Given the root of a binary tree with unique values and the values of two different nodes of the tree x and y, return true if the nodes corresponding to the values x and y in the tree are cousins, or false otherwise.

Two nodes of a binary tree are cousins if they have the same depth with different parents.

Note that in a binary tree, the root node is at the depth 0, and children of each depth k node are at the depth k + 1.

Example 1:

Input: root = [1,2,3,4], x = 4, y = 3
Output: false

Question 2) What will be the time and auxiliary space complexity of the following BFS approach?

Do a level order traversal of the tree using a queue.
For every node that is popped off the queue, check if the node is either Node x or Node y. If it is, then for the first time, set both siblings and cousins flags as true. The flags are set as true to mark the possibility of siblings or cousins.
To distinguish siblings from cousins, we insert markers in the queue. After inserting the children for each node, we also insert a null marker. This marker defines a boundary for each set of siblings and hence helps us to differentiate a pair of siblings from cousins.
Whenever we encounter the null marker during our traversal, we set the siblings flag to false. This is because the marker marks the end of the siblings territory.
The second time we encounter a node which is equal to Node x or Node y we will have clarity about whether or not we are still within the siblings boundary. If we are within the siblings boundary, i.e. if the siblings flag is still true, then we return false. Otherwise, we return true.