## Google Interview Question for Software Engineer / Developers

Country: United States

Comment hidden because of low score. Click to expand.
3
of 3 vote

There are three properties that must be satisfied for the array to be a binary tree:
*For every node, the binary tree property must be satisfied (left must be <= val, right must be >= val)
*There must be one node with no parents (the root)
*Every other node must have one parent.

We determine this by filling a hash table with the number of times each node is referenced by another; aka, the number of parents it has.

``````#include <vector>
#include <unordered_map>

bool IsBTree(std::vector<node>& nodes)
{
std::unordered_map<node*, int> counts;

for (int i = 0; i < (int)nodes.size(); i++)
{
if ((nodes[i].pLeft->val > nodes[i].val) || (nodes[i].pRight->val < nodes[i].val))
return false;
counts[nodes[i].pLeft]++;
counts[nodes[i].pRight]++;
}

int parentless = 0, singleParent = 0;
for (auto elt : counts)
{
parentless += elt.second == 0;
singleParent += elt.second == 1;
}
return ((parentless == 1) && (singleParent == nodes.size()-1));
}``````

Comment hidden because of low score. Click to expand.
3
of 3 vote

Following are the properties of the binary tree
1) each node can have at max two children.
2) each node in the tree has only one path from the root node reaching to it.

For this questions, we also have to make sure it is only one tree, not a set of trees, so the answer would be yes only when all the input nodes can be formed as one tree satisfying above two properties

Now, we can have two solutions

First one has O(N) time complexity and O(1) space complexity but it makes updates in tree data.
Here is how it goes

``````public boolean canForm(TreeNode[] Node)
{
int lowestval = 0;
foreach(TreeNode node in Node)
{
if (lowestval > node.val)
{
lowestval = node.val;
}
}
lowestval = lowestval - 100; // putting more lower value is not present in any of the nodes
foreach(TreeNode node in Node)
{
if(node.left != null)
{
if(node.left.val != lowestval)
{
node.left.val = lowestval;
}
else
{
return false;
}
}
if(node.right != null)
{
if(node.right.val != lowestval)
{
node.right.val = lowestval;
}
else
{
return false;
}
}
}
int rootnode = 0;
foreach(TreeNode node in Node)
{
if (node.val != lowestval)
{
rootnode++;
}
}
if(rootnode != 1)
{
return false;
}
return true;
}``````

The Second one has O(N) time complexity and O(N) space complexity where it does not updates in tree data.
Here is how it goes

``````public boolean canForm(TreeNode[] Node)
{
HashSet<TreeNode> hashset = new HashSet<TreeNode>();

foreach(TreeNode node in Node)
{
if(node.left != null)
{
if(hashset.Contains(node.left))
{
return false;
}
else
{
}
}
if(node.right != null)
{
if(hashset.Contains(node.right))
{
return false;
}
else
{
}
}
}
int rootnode = 0;
foreach(TreeNode node in Node)
{
if(!hashset.Contains(node))
{
rootnode++;
}
}
if(rootnode != 1)
{
return false;
}
return true;
}``````

Comment hidden because of low score. Click to expand.
1
of 1 vote

Criteria: each node has one parent except one node (which is root.)

We store the parent for each node in a hash. If the node appears more than once then it's not a binary tree.

At the end we check that the size of the hash is one less than the size of the input array.

``````class Node:
def __init__(self, val=0, left=None, right=None):
self.val = val
self.left = left
self.right = right

def canForm(nodes):
parents = dict() # child -> parent relationship, a child should appear at most once
for node in nodes:
if node.left is not None:
if node.left in parents:
return False
parents[node.left] = node

if node.right is not None:
if node.right in parents:
return False
parents[node.right] = node

return len(parents) == len(nodes) - 1``````

Comment hidden because of low score. Click to expand.
0
of 0 vote

I feel this question can be solved using Union Found

Comment hidden because of low score. Click to expand.
0
of 0 vote

Since based on this question's description, the author only lets us to confirm whether they can form a binary tree, so we only need to check whether it only has a single tree, so we can use Union Found algorithm to solve the question.

Comment hidden because of low score. Click to expand.
0
of 0 vote

What can be wrong with the nodes:
1. Several nodes have no parent.
2. The node is its own parent.
3. The node has left or right child that is not present in nodes.

``````#include <iostream>
#include <unordered_set>
#include <vector>

using namespace std;

class Node
{
public:
Node(int val)
: val_(val), left_(NULL), right_(NULL) {}
int val_;
Node *left_, *right_;
};

bool CanFormBinaryTree(const vector<Node*>& nodes)
{
unordered_set<Node*> children;
for (auto& n : nodes)
{
if (!n) {
return false;
}
if (n->left_)
{
if (n->left_ == n ||
children.find(n->left_) != children.end())
{
return false;
}
children.insert(n->left_);
}
if (n->right_)
{
if (n->right_ == n ||
children.find(n->right_) != children.end())
{
return false;
}
children.insert(n->right_);
}
}

// Each node is someone's child, except for the root
if (children.size() != nodes.size() - 1)
{
return false;
}

// For cases when a child is a node that doesn't exist in nodes
for (auto& n : nodes)
{
children.erase(n);
}
return children.empty();
}

int main() {
/*
(1)
/ \
(2)  (3)
/ \
(4) (5)
*/
Node n1(1), n2(2), n3(3), n4(4), n5(5);
n1.left_ = &n2;
n1.right_ = &n3;
n2.left_ = &n4;
n2.right_ = &n5;

cout << CanFormBinaryTree({&n1, &n2, &n3, &n4, &n5}) << "\n";
return 0;
}``````

Comment hidden because of low score. Click to expand.
0
of 0 vote

@tjcbs2. It looks lie the question is not about binary search tree. If it was about BST, the property of BST is something like "for each node in the tree, any value of the left subtree nodes must be < than the node's value, and any value of the right subtree nodes must be >= than the node's value".

Comment hidden because of low score. Click to expand.
-1
of 1 vote

``````bool CanForm(TreeNode[] ns) {
if(ns.Length == 0) return true;
var rs = new HashSet<TreeNode>(ns);
foreach(var n in ns) rs.Remove(n); // finding root elements
if(rs.Count() != 1) return false; // Non empty tree must have only one root

var n = rs[0];
var vt = new HashSet<node>(); // set of visited nodes to find cycles
var rst = new List<int>();

var hasCycle = InOrder(n, rst, vt);
if(hasCycle || rst.Count() != ns.Length) return false;
for(var i=0; i+1 < rst.Count(); i++){
if(ns[i]>ns[i+1]) return false;
}
return true;
}

bool InOrder(Node n, List<int> rst, HashSet<Node> vt){
if(!vt.Add(n)) return true; // found a cycle
if(n.left != null){
if(InOrder(n.left, rst, vt)) return true;
}

if(n.right != null){
if(InOrder(n.right, rst, vt)) return true;
}
return false;
}``````

Comment hidden because of low score. Click to expand.
-1
of 1 vote

Doesn't the question ask for checking only for binary tree(and not binary search tree)
Isn't it always possible to form a binary tree for list of such node

so answer can only be

``````Public boolean canForm(TreeNode[] nodes){
return true;
}``````

Comment hidden because of low score. Click to expand.
-1
of 1 vote

isn't the code just asking to check a 'binary tree', not binary search tree.?

Public boolean canForm(TreeNode[] nodes){
return true;
}

Comment hidden because of low score. Click to expand.
-1
of 1 vote

isn't the code just asking to check a 'binary tree', not binary search tree.?

``````Public boolean canForm(TreeNode[] nodes){
return true;
}``````

Comment hidden because of low score. Click to expand.
-1
of 1 vote

isn't the code just asking to check a 'binary tree', not binary search tree.?

``````Public boolean canForm(TreeNode[] nodes){
return true;
}``````

Comment hidden because of low score. Click to expand.
-2
of 2 vote

May be?

``if(rst[i]>rst[i+1]) return false;``

Name:

Writing Code? Surround your code with {{{ and }}} to preserve whitespace.

### Books

is a comprehensive book on getting a job at a top tech company, while focuses on dev interviews and does this for PMs.

### Videos

CareerCup's interview videos give you a real-life look at technical interviews. In these unscripted videos, watch how other candidates handle tough questions and how the interviewer thinks about their performance.