Recently I have created demo at http://www.algorithmdemos.com/trees/binary-Search-Tree.html to explain how Binary Search Tree works. Initially to draw binary search tree, I have used equal distance between nodes, Then I have seen overlapping of nodes as shown in below diagram.

Every node position will be based on its parent node position. If parent node is at (300, 0) then its child positions will be (250, 50) and (350, 50). Here X coordinate incremented or decremented by 50 and Y coordinate incremented by 50. Because of this approach I got overlapping problem as shown in above diagram. ( Node 6, 10 overlapping in the above diagram).In Balanced Binary Tree, nodes will increase in exponential way along with height. So we can decide X -coordinate of Tree Node using exponential decay. X coordinate factor will be decreased in exponential way

Height | Number of Nodes | Exponent (2 ^{(height - 1)} = number of nodes) | X coordinate factor |
---|---|---|---|

1 | 1 | ^{0} | NA |

2 | 2 | ^{1} | xfactor X (1/2)^{1} |

3 | 4 | ^{2} | xfactor X (1/2)^{2} |

4 | 8 | ^{3} | xfactor X (1/2)^{3} |

Observe the below diagram. Here I have taken X - factor as 300. The nodes were not overlapped because of exponential decay in distance.

## 0 comments:

## Post a comment