CODEWITHSUNDEEP
data-structuresbinary-tree
Ayush Singh Bhadoria
Ayush Singh Bhadoria

Reputation: 15

How this tree is valid

I was given this array as an input in a question[37,-34,-48,null,-100,-101,48,null,null,null,null,-54,null,-71,-22,null,null,null,8]

from this particular array, I can form a tree something like this

 37 -> L : -34, R: -48
-34 -> L : null, R: -100
-48 -> L; -101 R: 48
-100: L: null, R: null
-101-> L: null, R: null
48 -> L: -54, R: null
-54: L: -71, R: -22
-71 -> L: null, R: null
-22 -> L: null, R: 8
8 -> L: null, R, null

Where L and R represent the Left and right nodes of the binary tree respectively

Using the Tree visualizer we can also confirm this

You can click here for the visualization of the Binary Tree for the following input

But how can this be a valid tree because the last node 8 (at array index 18) should have a parent at index = 8 ( =int((18-1)/2) ), but there is a null at array index 8. I would be obliged if someone could confirm or correct me on this.

An array representation has the property that node i's child nodes are located in the array at 2k+1 (left child) and 2k+2 (right child)

for reference... https://inst.eecs.berkeley.edu/~cs61bl/r//cur/trees/array-repr.html?topic=lab20.topic&step=1&course=

Upvotes: 0

Views: 160

Answers (1)

Ahmed Lazhar
Ahmed Lazhar

Reputation: 866

There is no unique representation of tree using arrays, in the link you gave the representation should keep all nodes in the closest complete tree (so null nodes will have null children if they're not in the bottom level), but the algorithm used to generate the graph is different, it ignores cases under null nodes, this way makes the array smaller but less accessible (since accessing a parent or child node need to go through all previous nodes, the 2n, 2n+1, n/2 formulas do not work in this case)

Upvotes: 2

Related Questions