CODEWITHSUNDEEP
algorithmbinary-tree
user3127065
user3127065

Reputation: 31

How to create a binary tree that also links grandparents to grandchildren?

Is there is some algorithm to reach the grandchildren of a binary tree? Like the example?

enter image description here

In the picture, there are nodes linking grandparents to their grandchildren, whereas a normal binary tree only links children to parents. What algorithm would one use to link to grandparents?

EDIT: each node has an index and two values. [index] [value value];

What im trying to do:

index[3] and index[4] = value[0]; 
index[5] and index[6] = value[1]; 
index[7] and index[8] = value[2]; 
index[9] and index[10] = value[3]; 
.... ETC

Upvotes: 1

Views: 1116

Answers (2)

mmremann
mmremann

Reputation: 31

0
/ \

1 2

/ \ / \

3 4 5 6

[0,1,2,3,4,5,6] Binary Tree as Array

left = 2n+1

right = 2n+2

left-left-grandChild = 2(2n+1)+1 => 4n+3

left-right-grandChild = 2(2n+1)+2 => 4n+4

right-left-grandChild = 2(2n+2)+1 => 4n+5

right-right-grandChild = 2(2n+2)+2 => 4n+6

Upvotes: 1

A. I. Breveleri
A. I. Breveleri

Reputation: 767

Typically you construct each node in a binary tree with two pointers: a left child pointer 'node.left' and a right child pointer node 'node.right'. Then the four grandchildren of a node could be located with the expressions 'node.left.left', 'node.left.right', 'node.right.left', and 'node.right.right'. These expressions will evaluate very quickly.

Accessing the grandchildren via this technique will make everything much simpler for the person who has to maintain your code, which might even be you ten months from now after you have had time to forget that you ever had this discussion.

If you insist on storing the grandchild pointers redundantly then you will need four additional pointers per node: 'node.leftleft', 'node.leftright', 'node.rightleft', and 'node.rightright'.

This feels like the very definition a bad idea. Not only will the tree be big and clumsy, but every time you add or delete a node you will find yourself updating a metric barrowload of pointers. In order to recoup the time you will spend debugging such a mess, you will have to use the program for about nine thousand years.

Upvotes: 6

Related Questions