Leftist Tree - S-value

S-value

The s-value of a node is the distance from that node to the nearest leaf of the extended binary representation of the tree. The extended representation (not shown) fills out the tree so that each node has 2 children (adding a total of 5 leaves here). The minimum distance to these leaves are marked in the diagram. Thus s-value of 4 is 2, since the closest leaf is that of 8 --if 8 were extended. The s-value of 5 is 1 since its extended representation would have one leaf itself.

Read more about this topic:  Leftist Tree