Author |
Topic: Amazon - path to deepest 1 (Read 980 times) |
|
Ved
Junior Member
Gender: 
Posts: 53
|
 |
Amazon - path to deepest 1
« on: Mar 15th, 2010, 9:20am » |
 Quote  Modify
|
We have a binary tree (not a BST) made up of only 0s and 1s. we need to find the deepest 1 with a path from root made up only of 1's.
|
|
 IP Logged |
|
|
|
towr
wu::riddles Moderator
Uberpuzzler
Some people are average, some are just mean.
Gender:
Posts: 13730
|
|
Re: Amazon - path to deepest 1
« Reply #1 on: Mar 15th, 2010, 9:58am » |
Quote Modify
|
Just do depth first search for the deepest node while ignoring all child nodes with a 0.
|
|
IP Logged |
Wikipedia, Google, Mathworld, Integer sequence DB
|
|
|
AB
Newbie
Posts: 20
|
|
Re: Amazon - path to deepest 1
« Reply #2 on: Mar 15th, 2010, 9:44pm » |
Quote Modify
|
Code:int deepest(N,len)
{
if(N==null)
return -1;
l1 = deepest(N->left,len+1);
l2 = deepest(N->right,len+1);
if(N.val == 1)
return max(l1,l2,len);
else
return max(l1,l2);
}
|
|
Does this do ?? We get the farthest 1 from the root.
|
|
IP Logged |
|
|
|
mmgc
Newbie
Gender:
Posts: 47
|
|
Re: Amazon - path to deepest 1
« Reply #3 on: Mar 16th, 2010, 12:41am » |
Quote Modify
|
Do an in-order traversal...maintaining a variable MAX = Depth of node for which depth = sum of all nodes from root ( this sum can be maintained for each node traversed) ...
|
|
IP Logged |
|
|
|
towr
wu::riddles Moderator
Uberpuzzler
Some people are average, some are just mean.
Gender:
Posts: 13730
|
|
Re: Amazon - path to deepest 1
« Reply #4 on: Mar 16th, 2010, 2:29am » |
Quote Modify
|
on Mar 15th, 2010, 9:44pm, AB wrote:| Does this do ?? We get the farthest 1 from the root. |
|
You don't get a path from the root to that one which only has ones on it.
How about:
Code:void find_node2(treenode* root, treenode** dnode, int *maxdepth, int depth)
{
if(root && root->val == 1)
{
depth++;
if(depth > *maxdepth)
{
*maxdepth = depth;
*dnode = root;
}
find_node2(root->left, dnode, *maxdepth, depth);
find_node2(root->right, dnode, *maxdepth, depth);
}
}
treenode* find_node(treenode* root)
{
int maxdepth = 0;
treenode* dnode = null;
find_node2(root, &dnode, &maxdepth, 0);
return dnode;
}
|
|
|
| « Last Edit: Mar 16th, 2010, 2:29am by towr » |
IP Logged |
Wikipedia, Google, Mathworld, Integer sequence DB
|
|
|
AB
Newbie
Posts: 20
|
|
Re: Amazon - path to deepest 1
« Reply #5 on: Mar 16th, 2010, 3:00am » |
Quote Modify
|
Oh sorry. I misinterpreted the question. 
|
|
IP Logged |
|
|
|
|
RIDDLES SITE
WRITE MATH!
Home 
Help 
Search 
Members 
Login 
Register
Reply
Notify of replies
Send Topic
Print