#### Archived

This topic is now archived and is closed to further replies.

# Here is a simple yet complex problem...

## Recommended Posts

Imagine you have a full binary tree. Now number the nodes from top to bottom and from left to right in a row. A numbered tree would look like this: 0 / \ 1 2 / \ / \ 3 4 5 6 Now that you have the tree numbered this way, given a number, how would you get the path reaching that number?

##### Share on other sites
aaroncox1234    298
all the left nodes of your tree are odd, that might quicken things but a binary search tree would be better.

##### Share on other sites
Agony    3452
Is this homework? A challenge? Are you just curious?

If it''s something like that latter two, I''m game. ''Cause it''s actually quite simple. It''s a curious question, though, so I''ll be curious first.

##### Share on other sites
Anon Mike    1098
Smells like homework.

But as a hint trying looking at the binary representation of the node nubmer.

##### Share on other sites
SoulSpectre    169
this how to find the path:
//x is the number that we want to find the path too.

repeat till x = 0
if(!x%2) x = (x-2)/2 //number is even
else x = (x-1)/2
y[index++] = x

then when you reach 0 you will have the path in the reverse order. Ie from the node in question to the root.

##### Share on other sites
Thanks, that helped

##### Share on other sites
Agony    3452
We never did find out what it was for...

##### Share on other sites
To solve it in a more generic way use recursion.

#include <iostream>class Node{public: int number; Node* leftNode; Node*rightNode;public: Node(int num) {  number = num;  leftNode = 0;  rightNode = 0; } Node(Node& l, Node& r, int num) {  leftNode = &l;  rightNode = &r;  number = num; } bool getPath(int n) {  if (number == n ||      (leftNode && leftNode->getPath(m)) ||      (rightNode && rightNode->getPath(m)))  {   std::cout << number << "->";   return true;  }  else return false; }};int main(void){ Node a(Node(Node(Node(3)),Node(Node(4)),1),Node(Node(5),Node(6),2),0); int x = 3; //Node to find a.getPath(x); return 0;}

I hope that works... took me 3 minutes

(EDIT)
no, now it works... :D
(/EDIT)

[edited by - MadHed on May 26, 2004 5:18:08 PM]

##### Share on other sites
A tree that is numbered like that and full is a heap. A heap can be represented by an array with certain special properties.
It has to be a 1 indexed array or just waste one element (or the formula gets a little
more complex). But, Node #n is n+1st element of
the array. its children are elements 2n, and 2n+1 which correspond to nodes 2n-1 and 2n. its parent is
element n/2 (integer division) which corresponds to node n/2 -1, . So, to trace back, keep dividing the
node # by 2 until you reach 1. Of course, since your first
node is 0, you have to subtract 1 from each array element # along
the path.

##### Share on other sites
It is part of an assigment I have to do, unfortunantly it is just a small part of it.