many techniques exist for maintaining reasonably balanced bsts in the face of an unfriendly series of insert and delete operations one example is the avl tree of adelson-velskii and landiswhich is discussed by knuth [knu the avl tree (see section is actually bst whose insert and delete routines reorganize the tree structure so as to guarantee that the subtrees rooted by the children of any node will differ in height by at most one another example is the splay tree [st ]also discussed in section see bentley' programming pearl "thanksheaps[ben ben for good discussion on the heap data structure and its uses the proof of section that the huffman coding tree has minimum external path weight is from knuth [knu for more information on data compression techniquessee managing gigabytes by wittenmoffatand bell [wmb ]and codes and cryptography by dominic welsh [wel tables and are derived from welsh [wel exercises section claims that full binary tree has the highest number of leaf nodes among all trees with internal nodes prove that this is true define the degree of node as the number of its non-empty children prove by induction that the number of degree nodes in any binary tree is one less than the number of leaves define the internal path length for tree as the sum of the depths of all internal nodeswhile the external path length is the sum of the depths of all leaf nodes in the tree prove by induction that if tree is full binary tree with internal nodesi is ' internal path lengthand is ' external path lengththen for > explain why function preorder from section makes half as many recursive calls as function preorder explain why it makes twice as many accesses to left and right children (amodify the preorder traversal of section to perform an inorder traversal of binary tree (bmodify the preorder traversal of section to perform postorder traversal of binary tree write recursive function named search that takes as input the pointer to the root of binary tree (not bst!and value kand returns true if value appears in the tree and false otherwise write an algorithm that takes as input the pointer to the root of binary tree and prints the node values of the tree in level order level order first