<jupyter_start><jupyter_text>**Assignment 6** **Delivery Instructions**:  Similar to previous assignments. See this [**Canvas announcement**](https://njit.instructure.com/courses/11882/discussion_topics/42914) for more details.--- **Important Note**: If you want to follow the alternative track, as I explained in a previous discussions, you can skip questions marked with ^^. Please let me know that you do that !---- --- **Q1. Check BST validity**     Recall the definition of a the Node class which can be used for implementing binary trees. Write a function that takes as input such a tree $T$, and outputs True if $T$ is a valid BST, or False otherwise.  [Hint: Think recursion]<jupyter_code># your implementation goes here

class Node:
  def __init__(self,key):
    self.key = key
    self.lchild = None
    self.rchild = None 

# def checkBSTValidity(T):<jupyter_output><empty_output><jupyter_text>--- **Q2. Find the height of a Binary Tree**Write a function *BT_Height* that takes as input a binary tree and computes its height. [Hint: Again, think recursion]Side Note: If a BST is fully balanced then its height is exactly $\lceil \log_2 n \rceil$. So, the height computation allows you to check if a tree is fully balanced.<jupyter_code># your implementation goes here

# def BT_Height(T):<jupyter_output><empty_output><jupyter_text>--- **Q3.  Find the closest leaf**  Write a function *BT_ClosestLeaf* that takes as input a binary tree and computes the distance of the root to its closest leaf.<jupyter_code># your code goes here


# def BT_ClosestLeaf(T):<jupyter_output><empty_output><jupyter_text>--- **Q4^^**. Sorted array to BSTIn the lecture we briefly discussed that inserting keys in a random order, will give a balanced tree with high probability. However, it's likely that the tree will not be fully balanced. Suppose now that we have already a sorted array of elements $S$ and we want to convert it to a **fully** balanced search tree. Write a function that accomplishes that goal<jupyter_code># def sortedToBST(S)




# output should be a Tree.<jupyter_output><empty_output><jupyter_text>--- **Q5. Find Max in BST**Write a function *BST_max* that takes as input a BST and returns the maximum key in it. This function should be iterative.<jupyter_code># def BST_max(T):<jupyter_output><empty_output><jupyter_text>--- **Q6^^**. Check Red-Black Tree ValidityIn the following cell, I give the definition of a class that can be used to build Red-Black Trees. The *color* attribute is assumed to be 1 or 0, where 1 means 'black' and 0 means 'red'. Write a function *checkRBTreeValidity* that takes as input a RB Tree $T$ and outputs True if $T$ satisfies all RB properties we discussed in the lecture, and false otherwise. **Note 1**: As we discussed in the lecture the 'None' children are considered as black nodes without keys.  **Note 2**: Checking if a RB-Tree is a BST is also part of the question, but for it you can use Q1.<jupyter_code>class RBNode:
  def __init__(self,key):
    self.key = key
    self.lchild = None
    self.rchild = None 
    self.color = 1

# def checkRBValidity(T)<jupyter_output><empty_output>
{'fraction_non_alphanumeric': 0.08946195479146768, 'fraction_numerical': 0.008277618592804839, 'mean_word_length': 4.53169014084507, 'pattern_counts': {'":': 0, '<': 25, '<?xml version=': 0, '>': 25, 'https://': 1, 'lorem ipsum': 0, 'www.': 0, 'xml': 0}, 'pii_count': 0, 'substrings_counts': 0, 'word_list_counts': {'cursed_substrings.json': 0, 'profanity_word_list.json': 0, 'sexual_word_list.json': 0, 'zh_pornsignals.json': 0}}
{'chain_length': '6', 'dir': 'jupyter-structured-clean-dedup', 'id': '510359', 'license': 'Apache-2.0', 'n_tokens_mistral': 943, 'n_tokens_neox': 903, 'n_words': 428, 'path': 'notebooks/work/Assignment-6.ipynb', 'repo_name': 'cicorias/njit-alg-scratch', 'size': '3141'}