## unknown Interview Question

Software Engineers**Country:**United States

The solution can be designed with the following idea which runs in multiple passes:

Pass1: Read every node and for each node remember what other nodes are pointing to it using additional data structures

Pass2: Read every node to find the following:

a. Nodes who are pointed to by 0 other nodes ==> These are potential roots

b. Nodes who are pointed to by 1 nodes

c. Nodes who are pointed to by > 1 nodes

We have a valid binary tree iff:

1. The number of nodes whom nobody points to is 1 and that is the root

2. Every node is pointed to by at most one node

3. Starting with the root, and doing a DFS or a BFS covers all the nodes in the list

The solution can be designed with the following idea which runs in multiple passes:

Pass1: Read every node and for each node remember what other nodes are pointing to it using additional data structures

Pass2: Read every node to find the following:

a. Nodes who are pointed to by 0 other nodes ==> These are potential roots

b. Nodes who are pointed to by 1 nodes

c. Nodes who are pointed to by > 1 nodes

We have a valid binary tree iff:

1. The number of nodes whom nobody points to is 1 and that is the root

2. Every node is pointed to by at most one node

3. Starting with the root, and doing a DFS or a BFS covers all the nodes in the list

- Scott July 21, 2015