Recall that the height of a node u in a binary search tree (BST) T equals...

 

Transcribed Image Text:

Recall that the height of a node u in a binary search tree (BST) T equals the number of edges in the longest path from u to a leaf of the subtree rooted at u. (Leaves have height 0.) Define the radius of u to equal the number of edges in the shortest path from u to a leaf of the subtree rooted at u. We define a new notion of a balanced BST: a BST T is 2-balanced if, for every node u of T, height (u) 2 radius(u), where height(u) is the height of u in T, and radius(u) is the radius of u in T. Give a linear time algorithm that determines if a BST T is 2-balanced, according to the definition above. The algorithm's input is a pointer to the root of T, where each node u has the following fields: an integer u. key, and pointers u. lchild and u. rchild to the left and right child of u, respectively. (If u has no left or right child, the corresponding pointer is set to NIL.) There is no height or radius information already stored in any node. The algorithm's output is TRUE if T is 2-balanced, and FALSE otherwise. The worst-case running time of your algorithm must be O(n) where n is the number of nodes in T. Describe your algorithm by giving its pseudo-code, and explain why its worst-case running time is O(n). You do not need to prove that the algorithm is correct. Recall that the height of a node u in a binary search tree (BST) T equals the number of edges in the longest path from u to a leaf of the subtree rooted at u. (Leaves have height 0.) Define the radius of u to equal the number of edges in the shortest path from u to a leaf of the subtree rooted at u. We define a new notion of a balanced BST: a BST T is 2-balanced if, for every node u of T, height (u) 2 radius(u), where height(u) is the height of u in T, and radius(u) is the radius of u in T. Give a linear time algorithm that determines if a BST T is 2-balanced, according to the definition above. The algorithm's input is a pointer to the root of T, where each node u has the following fields: an integer u. key, and pointers u. lchild and u. rchild to the left and right child of u, respectively. (If u has no left or right child, the corresponding pointer is set to NIL.) There is no height or radius information already stored in any node. The algorithm's output is TRUE if T is 2-balanced, and FALSE otherwise. The worst-case running time of your algorithm must be O(n) where n is the number of nodes in T. Describe your algorithm by giving its pseudo-code, and explain why its worst-case running time is O(n). You do not need to prove that the algorithm is correct.

Answer rating: 100% (QA)

To determine if a Binary Search Tree BST T is 2balanced we can traverse the tree in a depthfirst man... View the full answer