Zillow Interview Question Software Engineer / Developers
Country: United States
Implement insert and delete in a tri-nary tree. Much like a binary-tree but with 3 child nodes for each parent instead of two -- with the left node being values < parent, the right node values > parent, and the middle node values == parent. For example, if I added the following nodes to the tree in this
order: 5, 4, 9, 5, 7, 2, 2 -- the tree would look like this:
5
/ | \
4 5 9
/ /
2 7
|
2
insertTree(node* root, int newValue)
{
if(root->value == newValue)
{
root->middle = getNode(newValue);
}
else if(root->value < newValue)
{
if(root->left ==null)
{
root->left = getNode(newValue);
}
else
{
insertTree(root->left,newValue);
}
}
else if(root->value > newValue)
{
if(root->right ==null)
{
root->right = getNode(newValue);
}
else
{
insertTree(root->right,newValue);
}
}
}
// TestSol.cpp : Defines the entry point for the console application.
//
struct tree
{
int data;
tree *right;
tree *left;
tree *middle;
};
tree* Create_tree(tree *root, int num)
{
if(root == NULL)
{
root = new tree();
root->data = num;
root->right = NULL;
root->left = NULL;
root->middle = NULL;
}
else if(num < root->data)
root->left = Create_tree(root->left, num);
else if(num == root->data)
root->middle = Create_tree(root->middle, num);
else
root->right = Create_tree(root->right, num);
return root;
}
int _tmain(int argc, _TCHAR* argv[])
{
//printf("%d %d", foo(NULL), foo("Hello@World, How are you?"));
tree *root = NULL;
int arr[] = {10,9,4,3,5,10,3,4,5,6,7,3,12,3,2,1};
for(int i=0; i<16; i++)
root = Create_tree(root, arr[i]);
return 0;
}
typedef struct TrinaryTree
{
struct TrinaryTree *Left;
struct TrinaryTree *Right;
struct TrinaryTree *Middle;
int Data;
} TriTree, *PTriTree;
void Insert(PTriTree *ppTree, int data)
{
if (ppTree)
{
if (!*ppTree)
{
*ppTree = new TriTree;
if (*ppTree)
{
(*ppTree)->Left = (*ppTree)->Right = (*ppTree)->Middle = NULL;
(*ppTree)->Data = data;
}
}
else
{
if ((*ppTree)->Data == data)
{
Insert(&(*ppTree)->Middle, data);
}
else
{
if ((*ppTree)->Data > data)
{
Insert(&(*ppTree)->Left, data);
}
else
{
Insert(&(*ppTree)->Right, data);
}
}
}
}
}
void DeleteHelper(PTriTree *ppTree)
{
PTriTree pTemp = NULL;
if (ppTree && *ppTree)
{
pTemp = *ppTree;
if ((*ppTree)->Left == NULL && (*ppTree)->Right == NULL && (*ppTree)->Middle == NULL)
{
*ppTree = NULL;
}
else
{
if ((*ppTree)->Middle != NULL)
{
*ppTree = (*ppTree)->Middle;
(*ppTree)->Left = pTemp->Left;
(*ppTree)->Right = pTemp->Right;
}
else
{
if (!(*ppTree)->Left)
{
*ppTree = (*ppTree)->Right;
}
else
{
if (!(*ppTree)->Right)
{
*ppTree = (*ppTree)->Left;
}
else
{
*ppTree = (*ppTree)->Right;
while ((*ppTree)->Left)
{
*ppTree = (*ppTree)->Left;
}
(*ppTree)->Left = pTemp->Left;
}
}
}
}
delete pTemp;
}
}
void Delete(PTriTree *ppTree, int data)
{
if (ppTree && *ppTree)
{
if ((*ppTree)->Data < data)
{
Delete(&(*ppTree)->Right, data);
}
else
{
if ((*ppTree)->Data > data)
{
Delete(&(*ppTree)->Left, data);
}
else
{
DeleteHelper(ppTree);
}
}
}
}
package Ques2;
public class TrinaryTree
{
private TreeNode root;
public TreeNode getRoot() {
return root;
}
public void setRoot(TreeNode root) {
this.root = root;
}
public void insert(int data)
{
TreeNode node = new TreeNode();
node.setData(data);
if (root == null)
{
root = node;
return;
}
else
{
TreeNode pointer = root;
while (pointer != null)
{
node.setParent(pointer);
if (pointer.getData() > data)
pointer = pointer.getLeft();
else if (pointer.getData() < data)
pointer = pointer.getRight();
else
{
pointer.setCount(pointer.getCount() + 1);
break;
}
}
pointer = node.getParent();
if (pointer.getData() > node.getData())
node.getParent().setLeft(node);
else if (pointer.getData() < node.getData())
node.getParent().setRight(node);
}
}
public boolean remove(int value)
{
TreeNode pointer = root;
if(pointer==null)
{
return false;
}
else
{
if(pointer.getData()==value){
if(pointer.getCount()>1)
{
pointer.setCount(pointer.getCount()-1);
return true;
}
else if(pointer.getCount()==1)
{
TreeNode children = pointer.getRight();
TreeNode child = children;
TreeNode previous = new TreeNode();
while(children!=null)
{
previous=children;
children = children.getLeft();
}
children=previous;
children.setData(child.getData());
child=null;
return true;
}
}
}
return false;
}
public void display(TreeNode root)
{
if(root==null)
{
return;
}
for(int i=1; i<=root.getCount(); i++)
{
System.out.println(root.getData());
}
display(root.getLeft());
display(root.getRight());
}
}
_________________________________________________________________
package Ques2;
public class TreeNode {
private int count=1;
private TreeNode parent;
private TreeNode left;
private TreeNode right;
private int data;
public int getData() {
return data;
}
public void setData(int data) {
this.data = data;
}
public int getCount() {
return count;
}
public void setCount(int count) {
this.count = count;
}
public TreeNode getParent() {
return parent;
}
public void setParent(TreeNode point) {
this.parent = point;
}
public TreeNode getLeft() {
return left;
}
public void setLeft(TreeNode left) {
this.left = left;
}
public TreeNode getRight() {
return right;
}
public void setRight(TreeNode right) {
this.right = right;
}
}
_____________________________________________________________
package Ques2;
public class mainClass {
/**
* @param args
*/
public static void main(String[] args) {
// TODO Auto-generated method stub
TrinaryTree tree = new TrinaryTree();
int [] a = {5, 4, 9, 5, 7, 2, 2};
for(int i = 0;i<a.length;i++)
{
tree.insert(a[i]);
}
tree.display(tree.getRoot());
System.out.println();
System.out.println();
boolean flag = tree.remove(5);
if(flag)
{
System.out.println("Element Removed Successfully");
tree.display(tree.getRoot());
}
else
{
System.out.println("Element Not Found");
}
}
}
You should complete the question!!
- nerd July 12, 2012