Google Interview Question
Software Engineer / DevelopersCountry: United States
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
{
hashset.Add(node.left);
}
}
if(node.right != null)
{
if(hashset.Contains(node.right))
{
return false;
}
else
{
hashset.Add(node.right);
}
}
}
int rootnode = 0;
foreach(TreeNode node in Node)
{
if(!hashset.Contains(node))
{
rootnode++;
}
}
if(rootnode != 1)
{
return false;
}
return true;
}
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
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;
}
@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".
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;
}
rst.Add(n.val);
if(n.right != null){
if(InOrder(n.right, rst, vt)) return true;
}
return false;
}
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.
- tjcbs2 March 28, 2017