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 thi
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 wrote:
> Given a binary tree(not a BST) find the 2 nodes of the binary tree
> which are separated by maximum distance.
> By distance, we mea
wont work for this tree:
x
/\
x x
/\
x x
/ \
xy
/ \
xx
/
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
Anki
yes, it is the diameter of the tree.
On Mon, May 30, 2011 at 1:17 AM, Vipul Kumar wrote:
> That is same as finding the diameter of the tree.
>
> On Mon, May 30, 2011 at 1:44 PM, Piyush Sinha
> wrote:
> > There can be two cases to it
> >
> > Case 1 - The maximum distance passes through the r
That is same as finding the diameter of the tree.
On Mon, May 30, 2011 at 1:44 PM, Piyush Sinha wrote:
> There can be two cases to it
>
> Case 1 - The maximum distance passes through the root node.
> 1
> / \
> 2 3
> /
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 i
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 gr