notes leftist trees leftist tree is tree which tends to ``lean'to the left the tendency to lean to the left is defined in terms of the shortest path from the root to an external node in leftist treethe shortest path to an external node is always found on the right every node in binary tree has associated with it quantity called its null path length which is defined as followsnull path and null path length consider an arbitrary node in some binary tree the null path of node is the shortest path in from to an external node of the null path length of node is the length of its null path sometimes it is convenient to talk about the null path length of an entire tree rather than of nodenull path length of tree the null path length of an empty tree is zero and the null path length of non-empty binary tree {rtltris the null path length its root when new node or subtree is attached to given treeit is usually attached in place of an external node since the null path length of tree is the length of the shortest path from the root of the tree to an external nodethe null path length gives lower bound on the cost of insertion examplethe running time for insertion in binary search treeis at least dt(compareo(dwhere is the null path length of the tree leftist tree is tree in which the shortest path to an external node is always on the right this informal idea is defined more precisely in terms of the null path lengths as followsdefinition (leftist treea leftist tree is binary tree with the following properties either lor {rtltr}where both tl and tr are leftist trees which have null path lengths dl and drrespectivelysuch that dl >dr figure shows an example of leftist heap leftist heap is simply heap-ordered leftist tree the external depth of the node is shown to the right of each node in figure the figure clearly shows that it is not necessarily the case in leftist tree that the number of nodes to the left of given node is greater than the number to the right howeverit is always the case that the null path length on the left is greater than or equal to the null path length on the right for every node in the tree lovely professional university