Career cup book question 4.8 - You are given a binary tree in which each
node contains a value. Design an algorithm to print all paths which sum up
to that value. Note that it can be any path in the tree - it does not have
to start at the root.
Answer given in career cup book -
Let’s approach
How to convert a Binary tree to BST ? Naive way is to create each node
of Binary tree one by one and keep on creating the BST.
--
You received this message because you are subscribed to the Google Groups
Algorithm Geeks group.
To post to this group, send email to algogeeks@googlegroups.com.
To
You are given a binary tree in which each node contains a value. Design an
ALGORITHM to print all paths which sum up to that value. Note that it can be
any path in the tree - it does not have to start at the root.
--
*prasanth*
--
You received this message because you are subscribed to the
hi prasanth,
i was asked a similar ques but with the condition that path shud terminate
at a leaf node u just have to return true if you are able to find a path.
what i did was,
- do an inorder traversal (u have to pass a parameter that represents
sum as well along with treenode pointer)
for your question -
On Sun, Sep 18, 2011 at 3:44 PM, abhishek sharma abhishek.p...@gmail.comwrote:
hi prasanth,
i was asked a similar ques but with the condition that path shud terminate
at a leaf node u just have to return true if you are able to find a path.
what i did was,
- do
You are given a binary tree in which each node contains a value. Design an
ALGORITHM to print all paths which sum up to that value. Note that it can be
any path in the tree - it does not have to start at the root.
--
*prasanth*
--
You received this message because you are subscribed to the
Print the coordinates of nodes of a binary tree.
eg. A
BC
D EF G
A(3,2)
B(1,1)
C(5,1)
D(0,0)
E(2,0)
F(4,0)
G(6,0)
*Snehil Saxena
NIT Warangal
3rd yr*
--
You received this message because you are subscribed to the
Try traversing in LEVEL order and maintain array for each level...(Levels
can be found by height of tree)
then try by calculating sums starting from root(level zero) to higher level.
Its typical to explain here but i found it as a solution and that will
definitely found the solution.
On Thu, Jun
My approach :
int FindPath(Node n , sum s )
{
FindPath(n-left , s ) ||
FindPath(n-right , s) ||
OneOf { a1 = AllSumsFromLeafToRoot( n-left ) } + n-value +
Oneof { a2 = AllSumsFromLeafToRoot( n-right ) == s ) }
// Use a1 and a2 to find out the actual path
}
Here all possible
How to find a path in a given binary tree which sums up to a given target
value?
for example if the given BT is
5
/ \
3 2
/
7
and if the target is 10, then the path is root(5) + left node(3) +
right node (2).
--
You received this message because you are subscribed to the Google
7+3 also give the sum to be 10???
On 6/29/11, Akshata Sharma akshatasharm...@gmail.com wrote:
How to find a path in a given binary tree which sums up to a given target
value?
for example if the given BT is
5
/ \
3 2
/
7
and if the target is 10, then the path is root(5) +
The idea is to traverse the binary tree in post order and find out all
the path sums and store them. Use a hashtable or any other data
structure to store the possible paths rooted at a node and going
down-only. Now we can construct all paths going through a node from
itself and its childrens'
I don't have any alternative solution till now.
On Wed, Jun 29, 2011 at 8:05 PM, varun pahwa varunpahwa2...@gmail.comwrote:
@ankit: ur space complexity will be too high. i think it will be ultimately
2^n where n is the number of the nodes.
On Wed, Jun 29, 2011 at 1:10 PM, ankit sambyal
By traversing tree either preorder or inorder or postorder and storing the
partial sums along the way and comparing the partial sums with the required
sum can solve the problem
On Wed, Jun 29, 2011 at 7:56 PM, Akshata Sharma
akshatasharm...@gmail.comwrote:
How to find a path in a given binary
Sunny, the solution is great. Could you give me some ideas around how
do you approach such problems in recursive manner?
Recursion is never easy for me to understand as it is difficult to visualize.
On Tue, Jun 21, 2011 at 11:52 PM, sunny agrawal sunny816.i...@gmail.com wrote:
see this
can this be also calculated as first calculate the diameter of the tree then
add the number of nodes in the path of the the root of the tree to the root
of the sub tree of which the diameter is calculated.
On Thu, Jun 23, 2011 at 3:06 AM, Jitendra singh jsinghrath...@gmail.comwrote:
@ Anantha
@ Anantha Krishnan
yeah , you are right .I misinterpreted it.Your solution is
right(actually my algo has no bug but I am returning 2 max out of 4
values . It is sure that one value will come from right and one from
left side.So no need to take take struct ret_ele .function returning
single
I modified Sunny's code to get Node X and Node Y.
http://ideone.com/YF9qi
Can we do better than this?
Thanks Regards,
Anantha Krishnan
On Wed, Jun 22, 2011 at 11:11 AM, oppilas . jatka.oppimi...@gmail.comwrote:
Sunny,
Can but can we modify this code to get the *node X and node Y*?.
On
Hi All,
I have written code for finding diameter of a binary tree here
http://ideone.com/WHg9t
Is it correct? Do I need to make any changes there?
Thanks Regards
Anantha Krishnan
--
You received this message because you are subscribed to the Google Groups
Algorithm Geeks group.
To post to
I think this solution is wrong .
Because
for the case -
1
5 8
10030010
ans should be 406
But above code gives 124
On 6/22/11, Anantha Krishnan ananthakrishnan@gmail.com wrote:
I modified Sunny's code to get Node X and Node Y.
Solution should be-
each node has three values
1) root_cur
2)cur_fleaf
3)cur_sleaf
strcut ret_ele
{
largest;
second_largest
}
ret_ele solve(node,sum_root_cur)
{
if(node==rootroot==NULL)
{
sum_root_cur=0;
return;
}
root_cur=sum_root_cur
@Jitendra
Both are working fine
Which code r u talking about?
On Thu, Jun 23, 2011 at 2:19 AM, Jitendra singh jsinghrath...@gmail.comwrote:
Solution should be-
each node has three values
1) root_cur
2)cur_fleaf
3)cur_sleaf
strcut ret_ele
{
largest;
second_largest
}
ret_ele
@Jitendra
I guess your tree construction is wrong.
You can verify by replacing the Construct function with this:
*void Construct() {*
*Node* d = new Node(100);*
*Node* e = new Node(300);*
*Node* g = new Node(10);*
*Node* b = new Node(5, d, e);*
*Node* c =
Hi All,
Given a binary tree, find 2 leaf nodes say X and Y such that F(X,Y) is
maximum where F(X,Y) = sum of nodes in the path from root to X + sum of
nodes in the path from root to Y - sum of nodes in the common path from root
to first common ancestor of the Nodes X and Y.
Any ideas.
Thanks
i am assuming all nodes have positive values..
Keep a buffer of all the leaf nodes..take two leaf nodes and find the
LCA..compute sum from root to LCA and subtract it from the sum of nodes from
root to the leaves...store all the sums and find maximum out of it..
On Tue, Jun 21, 2011 at 4:52 PM,
@Piyush
good to start with
But i think a recursive O(n) is possible
in downward calls pass sum from root to node
and on return calls pass sum from leafs to root of each subtree and using
this collective information updating a global ans max.
On Tue, Jun 21, 2011 at 5:05 PM, Piyush Sinha
Thanks.
I expect more details in implementation point of view.
Thanks Regards,
Anantha Krishnan
On Tue, Jun 21, 2011 at 6:41 PM, sunny agrawal sunny816.i...@gmail.comwrote:
@Piyush
good to start with
But i think a recursive O(n) is possible
in downward calls pass sum from root to node
and
see this
*
https://ideone.com/1ZtIq*
On Tue, Jun 21, 2011 at 10:23 PM, Anantha Krishnan
ananthakrishnan@gmail.com wrote:
Thanks.
I expect more details in implementation point of view.
Thanks Regards,
Anantha Krishnan
On Tue, Jun 21, 2011 at 6:41 PM, sunny agrawal
@sunny agrawal
*Thanks a lot.*
*Great code. I got the logic now.Thanks again.*
*
*
Thanks Regards,
Anantha Krishnan
On Tue, Jun 21, 2011 at 11:52 PM, sunny agrawal sunny816.i...@gmail.comwrote:
see this
*
https://ideone.com/1ZtIq*
On Tue, Jun 21, 2011 at 10:23 PM, Anantha Krishnan
Sunny,
Can but can we modify this code to get the *node X and node Y*?.
On Wed, Jun 22, 2011 at 8:32 AM, Anantha Krishnan
ananthakrishnan@gmail.com wrote:
@sunny agrawal
*Thanks a lot.*
*Great code. I got the logic now.Thanks again.*
*
*
Thanks Regards,
Anantha Krishnan
On Tue,
check for a*ao*,even tough they are search heuristics, some modification of
the algorithm would solve the problem.
On Mon, May 30, 2011 at 12:56 AM, ross jagadish1...@gmail.com wrote:
Given a binary tree(not a BST) find the 2 nodes of the binary tree
which are separated by maximum distance.
Given a binary tree(not a BST) find the 2 nodes of the binary tree
which are separated by maximum distance.
By distance, we mean no. of edges in the path from node1 to node2.
--
You received this message because you are subscribed to the Google Groups
Algorithm Geeks group.
To post to this
There can be two cases to it
Case 1 - The maximum distance passes through the root node.
1
/ \
2 3
/ \
45
Maximum distance is between 4 and 5 i.e. 4
Case 2 - The maximum distance lies
That is same as finding the diameter of the tree.
On Mon, May 30, 2011 at 1:44 PM, Piyush Sinha ecstasy.piy...@gmail.com wrote:
There can be two cases to it
Case 1 - The maximum distance passes through the root node.
1
/ \
2 3
yes, it is the diameter of the tree.
On Mon, May 30, 2011 at 1:17 AM, Vipul Kumar vipul.k.r...@gmail.com wrote:
That is same as finding the diameter of the tree.
On Mon, May 30, 2011 at 1:44 PM, Piyush Sinha ecstasy.piy...@gmail.com
wrote:
There can be two cases to it
Case 1 - The
Here's the crude algo :
First find the node having the max depth in the left sub tree and then find
the node having the max depth in the right sub tree. Ties are broken
arbitrarily.
These will be the 2 nodes separated by the maximum distance. The sum of
their depths will give us the distance
wont work for this tree:
x
/\
x x
/\
x x
/ \
xy
/ \
xx
/
I dont see any property of binary tree which u can take advantage of to
convert the binary tree to a BST.
On Tue, Mar 22, 2011 at 9:31 PM, Decipher ankurseth...@gmail.com wrote:
Convert Binary tree to BST in most efficient way ?
--
You received this message because you are subscribed to
Convert Binary tree to BST in most efficient way ?
--
You received this message because you are subscribed to the Google Groups
Algorithm Geeks group.
To post to this group, send email to algogeeks@googlegroups.com.
To unsubscribe from this group, send email to
Why should we start traversing towards right ?
root will be the ultimate parent anyways . May be I din get your
approach .Can you elaborate with an example as given by the Thread
starter ?
For vertical level 1 . The node is 10 and hence the sum is 10 .
For vertical line 2 (level 2) , going left
Given a binary tree with no size limitation, write a program to find
the sum of each vertical level and store the result in an appropriate
data structure (Note: You cannot use an array as the tree can be of
any size).
4
use hash
take an array verticalsum[]={0};
the function will be like this
void vertcal_sum(node *root, int level){
if(root!=NULL){
verticalsum[level]+=root-data;
vertcal_sum(root-left,level-1);
vertcal_sum(root-left,level+1);
}
}
On Mon,
It would be
*vertcal_sum(root-right,level+1);
*in the last line
--
Tushar Bindal
Computer Engineering
Delhi College of Engineering
Mob: +919818442705
E-Mail : tusharbin...@jugadengg.com, tushicom...@gmail.com
--
You received this message because you are subscribed to the Google Groups
Claim: any given vertical line will start with a node.(This is obvious)
Divide this problem into 2 subparts.
1st: Finding the starting node of given line.
2nd : finding the required sum.
Let T be the tree and L be the given level.
For 1st part: Find the leftmost node of the given tree,T.This
HAD MISSED OUT SOPME THINGS IN PREVIOUS REPLY.
SORRY GUYS
hereby i rectify the mistakes:
Claim: any given vertical line will start with a node.(This is obvious)
Divide this problem into 2 subparts.
1st: Finding the starting node of given line.
2nd : finding the required sum.
Let T
@tushar thnxx for correction :D
On Mon, Feb 14, 2011 at 7:50 PM, SEHAJ SINGH KALRA sehaj...@gmail.comwrote:
HAD MISSED OUT SOPME THINGS IN PREVIOUS REPLY.
SORRY GUYS
hereby i rectify the mistakes:
Claim: any given vertical line will start with a node.(This is obvious)
Divide
How to check whether the left subtree is an exact mirror of the right
subtree using iterative methods.
--
You received this message because you are subscribed to the Google Groups
Algorithm Geeks group.
To post to this group, send email to algoge...@googlegroups.com.
To unsubscribe from this
hi, i need to find the number of nodes at each level of a binary tree..the
binary tree may not be balanced..
output:
Level 0 - 1 node
Level 1 - 2 nodes
Level 2- 3 nodes
and so on..based on the tree structure..I am not able to count at each
level..pls suggest a way to do that.
--
Harshal
If we consider the edges in binary tree as threads and nodes in the
tree as weights hanging from it(it is suspended from the root) then
how the tree structure will change when the tree is hung from a
particular leaf.
--
You received this message because you are subscribed to the Google Groups
1) Suppose the node which you hold is P
2) Navigate on path from P to Root of Tree[Upside] and flip the relationship
direction for every edge you encounter on the path
3) Make P as Root of tree
4) redraw(P);
-Regards
Amit Agarwal
blog.amitagrwal.com
On Fri, Oct 8, 2010 at 1:29 PM, snehal jain
Give all possible methods to flatten a binary tree to a linked list.
for eg.
50
/ \
25 60
/ \ / \
530 55 75
should be flattened to 5-25-30-50-55-60-75
PS: note that the tree should be converted to the LL and no separate
LL should be formed.
--
You
I can only figure out the inorder traversal...
On Thu, Aug 26, 2010 at 9:59 AM, krazee koder aravindhr...@gmail.com wrote:
Give all possible methods to flatten a binary tree to a linked list.
for eg.
50
/ \
25 60
/ \ / \
5 30 55 75
should be flattened
Am 26.08.2010 18:59, schrieb krazee koder:
Give all possible methods to flatten a binary tree to a linked list.
for eg.
50
/ \
25 60
/ \ / \
530 55 75
should be flattened to 5-25-30-50-55-60-75
PS: note that the tree should be converted to the
No, you are wrong here.
The inorder sequence should be 5 - 25 - 30 - 50 - 55 - 60 -75.
The preorder sequence should be 50 - 25 - 5 - 30 - 60 - 55 - 75
The postorder sequence should be 5 - 30 - 25 - 55 - 75 - 60 - 50
Below is the analysis (from wikipedia):
To traverse a non-empty binary tree
At first, store the pointer to the first node in inorder traversal (in this
case 5) because its going to be the head of the list.
Then use the following logic.
flattenTree(TreeNode node) {
if (node is leaf node)
return node;
if (node.left exists) then
A binary tree with each node has an additional field node which is
initialized to be NULL at first. Asked to, for each node, point its
next pointer to the next node in level-by-level traversal order. NO
QUEUE should be used HERE!
--
You received this message because you are subscribed to the
Given two binary trees T1 and T2 , with duplicates allowed. Write a program
to decide whether the T2 is a subtree of T1. T1 has millions of nodes and T2
has hundreds of nodes.
--
With Regards,
Jalaj Jaiswal
+919026283397
B.TECH IT
IIIT ALLAHABAD
--
You received this message because you are
use recursion
On Fri, Jun 18, 2010 at 8:53 AM, Anurag Sharma anuragvic...@gmail.comwrote:
Here is the link which fits your need.
http://www.coders2020.com/construct-a-tree-given-its-inorder-and-preorder-traversal-strings-similarly-construct-a-tree-given-its-inorder-and-post-order
Anurag
1) Pick an element from Preorder. Increment a Preorder Index Variable
(preIndex in below code) to pick next element in next recursive call.
2) Create a new tree node tNode with the data as picked element.
3) Find the picked element’s index in Inorder. Let the index be inIndex.
4) Call buildTree
write a code to construct tree from inorder nd preorder traversal..
--
You received this message because you are subscribed to the Google Groups
Algorithm Geeks group.
To post to this group, send email to algoge...@googlegroups.com.
To unsubscribe from this group, send email to
Here is the link which fits your need.
http://www.coders2020.com/construct-a-tree-given-its-inorder-and-preorder-traversal-strings-similarly-construct-a-tree-given-its-inorder-and-post-order
Anurag Sharma
On Thu, Jun 17, 2010 at 4:34 PM, divya sweetdivya@gmail.com wrote:
write a code to
For traversing binary trees there are standard ways like,
- In order
- Pre Order
- Post Order
Questions Are:
The construction of the data as a binary tree is upto us. Am I right?
(I read somewhere 2n-n combinations are possible)
Is there any thing like it should be always ordered or sorted?
hi friends
I want to know ,how to write a C function to traverse a binary tree
level by level. In each level,the tree is traversed from left to right.
--~--~-~--~~~---~--~~
You received this message because you are subscribed to the Google Groups
Algorithm
Hi,
Is that in-order search of BST = depth first search?
thanks.
--~--~-~--~~~---~--~~
You received this message because you are subscribed to the Google Groups
Algorithm Geeks group.
To post to this group, send email to algogeeks@googlegroups.com
To
64 matches
Mail list logo
