1
$\begingroup$

Imagine I have a binary heap, traversed in a breadth first manner like so:

                  0
       1          |           2
  3    |    4     |    5      |     6
7 | 8  |  9 | 10  |  11 | 12  |  13 | 14

To the left of root (0) is 1, to the right is 2, to the left of 1 is 3 to it's right is 4 etc.

So node 13 corresponds to the following pattern (right right, left, (or 0,0,1, perhaps)).

The question is, is there an equation, function, or algorithm that will produce the pattern to get to any node without actually producing the entire tree and traversing it?

Say I didn't create the tree in memory (it's just a virtual tree). How would I know that in order to get to 8 I need to start at root and go: left,left, right (1,1,0)?

Is this computable without creating the tree, and traversing it? If so what is the pattern for 42? is it easily calculable (is it linear) ?

I'm sorry for not knowing all the CS terms (I'm not a cs major, but I want to know if there's a deterministic algorithm to produce a path to any node, if so, whats it's computational efficiency) ?

$\endgroup$
  • $\begingroup$ You say you meant heap rather than tree. Please edit the question to remove all references to a tree, and to have correct statements. Please don't use "stuff EDIT: I actually meant something different"; instead, just change the question to what you meant. See cs.meta.stackexchange.com/q/657/755. $\endgroup$ – D.W. Sep 27 '18 at 21:46
3
$\begingroup$

Binary trees can have different structures. Every node can have at most two children. At most means you might have 2 children, you might have one child or no child. This leads to different structural possibilities for the binary tree.

There is no definite pattern to tell how to find a particular node. Closest you can get to a pattern is when you have a binary heap, but in a heap it is fix that the binary tree will be complete binary tree i.e. all the internal nodes will have two children and the leaf nodes at the last level will be as left as possible. For a heap you can determine the left child as $2*i + 1$ and right child as $2*i+2$ where $i$ is the index of node and $i = 0$ for root node.

In the worst case a binary tree can degenerate to a linked list which means you would have to proceed linearly to find the element you want. So, we can say how will the search of a node proceed totally depends on the structure of the binary tree.

To find a node basically traverse the tree with any of DFS or BFS.

$\endgroup$
  • $\begingroup$ ah! thank you, I really meant a binary heap, thank you for helping me understand the particulars of what I am looking for :) Okay, so I now understand how to use that equasion to get the left and right of any node, awesome! but is there an equasion to get the parent? that seems much harder, but it also seems like it should be determinable. Is there a calculation to get the parent of any node? $\endgroup$ – Legit Stack Sep 27 '18 at 20:22
  • 1
    $\begingroup$ If you got to child, you can get the parent as well. Just try a bit. You will get it. $\endgroup$ – Navjot Waraich Sep 27 '18 at 20:25
2
$\begingroup$

As far as I have understood your question, you are looking for an algorithm that gives you the sequence of operation, given the number, if numbers arranged as you have mentioned. For example what will be operations to reach the number 42. If that's the case:

  1. First thing to consider is whether the no. X is even or odd. If X Is even then last operation would be right Else last operation would be left.

    E.g. 13 is odd so last operation from. Its parent will always be left. If it's an even no. e.g. say 8, The last operation is right. For 42 last operation should be right.

  2. Next what will be X's parent? If X is even X/2 - 1 else (X-1)/2 For 42: parent = 20

Now you have got the parent, just check how to reach the parent by following step 1. Keep on doing till you get 0.

For 42 : 1 4 9 20 42 So : left right left right right

Complexity: How many times you can halve X to make it reach 0? What should be power of 2 to make it X? Ans : log X (base 2).

$\endgroup$
  • $\begingroup$ Thank you @aknautiyal you described what I figured out given the other answer. So yes this is what I was looking for, but now that I have that I generalized it to and base tree, not just binary. But now I'm wondering if one could generalize (this ability to quickly calculate the path to a given node) to any non symmetrical tree of a repeating pattern. For instance, a tree where the left node has two children and the right node has 3, and on right nodes, the center has one child. I'm not sure it's possible to which find a path from node to root given a tree like that. $\endgroup$ – Legit Stack Sep 30 '18 at 13:59

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.