<jupyter_start><jupyter_text>Binary tree<jupyter_code>class Tree_node:
    def __init__(self, key):
        self.key = key
        self.right = None
        self.left = None<jupyter_output><empty_output><jupyter_text>let's create objects representing each node of the tree<jupyter_code>node0 = Tree_node(3)
node1 = Tree_node(4)
node2 = Tree_node(5)
node0
node0.key<jupyter_output><empty_output><jupyter_text>we can connect th node by setting the `.left` and `.right` properties of root nde<jupyter_code>node0.left = node1
node0.right = node2<jupyter_output><empty_output><jupyter_text>and we are done<jupyter_code>tree = node0<jupyter_output><empty_output><jupyter_text>tree.key<jupyter_code>tree.left
tree.left.key
tree.right.key<jupyter_output><empty_output><jupyter_text>![Capture.PNG](attachment:Capture.PNG) it's bit inconvenient to create tree manually connecting all nodes. let's write helper function to convert with a structure<jupyter_code>tree_tuple = ((1, 3, None), 2, ((None, 3, 4), 5, (6, 7, 8)))
def parse_tuple(data):
    #print(data)
    if isinstance(data, tuple) and len(data) == 3:
        node = Tree_node(data[1])
        node.left = parse_tuple(data[0])
        node.right = parse_tuple(data[2])
    elif data is None:
        node = None
    else:
        node = Tree_node(data)
    return node
tree2 = parse_tuple(tree_tuple)
tree2<jupyter_output><empty_output><jupyter_text>we can now examine the tree to verify that it was constructed as expected<jupyter_code>tree2.key
tree2.left.key
tree2.left.key, tree2.right.key
def display_keys(node, space='\t', level = 0):
    #print nodes
    
    #if node is empty
    if node is None:
        print(space * level + 'X')
        return
        
    #if the node is a leaf
    if node.left is None and node.right is None:
        print(space * level + str(node.key))
        return
    
    #if node has children
    display_keys(node.right, space ,level + 2)
    print(space * level + str(node.key))
    display_keys(node.left, space, level + 2)
display_keys(tree2, '  ')<jupyter_output>8
        7
            6
    5
            4
        3
            X
2
        X
    3
        1<jupyter_text>Example 2 ![tree2.png](attachment:tree2.png)<jupyter_code>tree_tuple1 = (((3, 5, (6, 8, None)), 10, (12, 13, (None, 18, 21))))
tree3 = parse_tuple(tree_tuple1)
tree3
tree3.key
display_keys(tree3, '  ')<jupyter_output>21
        18
            X
    13
        12
10
            X
        8
            6
    5
        3<jupyter_text>*** Trvarsing Binary Tree frequently asked in coding interview and assessments **Question 1** : write a function to perform the _inorder_ traversal of binary tree.    **Question 2**: write a function to perform the _preorder_ traversal of binary tree.**Question 3**: write a function to perform the _postorder_ traversal of binary tree      Inorder Trversal1. left2. root3. right  Preorder Traversal1. root2. left3. right  Postorder Traversal1. left2. right3. root implementation of inorder traversal of a binary tree<jupyter_code>def traverse_in_order(node):
    if node is None:
        return []
    return(traverse_in_order(node.left) +
           [node.key] +
          traverse_in_order(node.right))<jupyter_output><empty_output><jupyter_text>Let's try out with this tree ![Capture.PNG](attachment:Capture.PNG)<jupyter_code>tree = parse_tuple(tree_tuple)
display_keys(tree)
traverse_in_order(tree)<jupyter_output><empty_output><jupyter_text>implementation of preorder traversal<jupyter_code>def traverse_pre_order(node):
    if node is None:
        return []
    return([node.key] +
           traverse_pre_order(node.left) +
           traverse_pre_order(node.right))
traverse_pre_order(tree)<jupyter_output><empty_output><jupyter_text>implementation postorder traversal<jupyter_code>def traverse_post_order(node):
    if node is None:
        return []
    return(traverse_post_order(node.left) +
           traverse_post_order(node.right) +
          [node.key])
traverse_post_order(tree)<jupyter_output><empty_output><jupyter_text>*** Height and Size of Binary Tree **Question 4:** write a function to calculate the height/depth of binary tree**Question 5:** write a function to count the number of nodes in binary tree<jupyter_code>def tree_height(node):
    if node is None:
        return 0
    return 1 + max(tree_height(node.left), tree_height(node.right))<jupyter_output><empty_output><jupyter_text>let's compute the height of this tree ![tree2.png](attachment:tree2.png)<jupyter_code>tree_height(tree3)<jupyter_output><empty_output><jupyter_text>here's a function to count the number of nodes in a binary tree<jupyter_code>def tree_size(node):
    if node is None:
        return 0
    return 1 + tree_size(node.left) + tree_size(node.right)
tree_size(tree3)<jupyter_output><empty_output><jupyter_text>As a final step, compile all the functions we've written so far as methods within the `Tree_node`. Encapsulation of data and functionality within the same class is a good practice<jupyter_code>class Tree_node:
    def __init__(self, key):
        self.key = key
        self.right = None
        self.left = None
        
    #inorder traversal --> (left, root, right)    
    def traverse_in_order(node):
        if node is None:
            return []
        return(traverse_in_order(node.left) +
               [node.key] +
               traverse_in_order(node.right))
    
    #preorder traversal --> (root, left, right)
    def traverse_pre_order(node):
        if node is None:
            return []
        return([node.key] +
               traverse_pre_order(node.left) +
               traverse_pre_order(node.right))
    
    #postorder traversal --> (left, right, root)
    def traverse_post_order(node):
        if node is None:
            return []
        return(traverse_post_order(node.left) +
               traverse_post_order(node.right) +
               [node.key])
    
    #to find height of tree
    def tree_height(node):
        if node is None:
            return 0
        return 1 + max(tree_height(node.left), tree_height(node.right))
    
    #count no of elements in tree
    def tree_size(node):
        if node is None:
            return 0
        return 1 + tree_size(node.left) + tree_size(node.right)
    
    #conversion tree to tuple
    def to_tuple(self):
        if self is None:
            return None
        if self.left is None and self.right is None:
            return self.key
        return Tree_node.to_tuple(self.left), self.key, Tree_node.to_tuple(self.right)
    
    def __str__(self):
        return "Binary Tree <{}> ".format(self.to_tuple())
    
    def __repr__(self):
        return "Binary Tree <{}> ".format(self.to_tuple())
    
    def parse_tuple(data):
        #print(data)
        if isinstance(data, tuple) and len(data) == 3:
            node = Tree_node(data[1])
            node.left = parse_tuple(data[0])
            node.right = parse_tuple(data[2])
        elif data is None:
            node = None
        else:
            node = Tree_node(data)
        return node
    
    def display_keys(node, space='\t', level = 0):
        #print nodes
        
        #if node is empty
        if node is None:
            print(space * level + 'X')
            return
        
        #if the node is a leaf
        if node.left is None and node.right is None:
            print(space * level + str(node.key))
            return
        
        #if node has children
        display_keys(node.right, space ,level + 2)
        print(space * level + str(node.key))
        display_keys(node.left, space, level + 2)
tree_tuple
tree4 = Tree_node.parse_tuple(tree_tuple)
tree4
tree4.display_keys('   ')
tree4.tree_height()
tree4.tree_size()
tree4.traverse_in_order()
tree4.traverse_pre_order()
tree4.traverse_post_order()
tree4.to_tuple()<jupyter_output><empty_output><jupyter_text>*** Binary Search Tree A binary search tree or BST is binary tree that satisfies the following conditions:1. The left subtree of any node only contains nodes with keys less than the root node2. The right subtree of any node only contains nodes with keys greater than the root node  **Question 6:** write a function to check if a binary tree is BST**Question 7:** write a function to find the maximum key in a binary tree**Question 8:** write a function to find the minimum key in a inary tree ![name_tree.png](attachment:name_tree.png) solution:<jupyter_code>def remove_none(nums):
    return [x for x in nums if x is not None]

def is_bst(node):
    if node is None:
        return True, None, None
    
    is_bst_l, min_l, max_l = is_bst(node.left)
    is_bst_r, min_r, max_r = is_bst(node.right)
    
    is_bst_node = (is_bst_l and is_bst_r and
                  (max_l is None or node.key > max_l) and
                  (min_r is None or node.key < min_r))
    
    min_key = min(remove_none([min_l, node.key, min_r]))
    max_key = max(remove_none([max_l, node.key, max_r]))
    
    #pint(node.key, min_key, max_key, is_bst_none)
    
    return is_bst_node, min_key, max_key<jupyter_output><empty_output><jupyter_text>![Capture.PNG](attachment:Capture.PNG) let's verify this using `is_bst`<jupyter_code>tree4
is_bst(tree4)
tree5 = Tree_node.parse_tuple((('akash', 'baban', 'harsh'), 'jayesh', ('sid', 'sonali', 'vishal')))
tree5.display_keys()
is_bst(tree5)<jupyter_output><empty_output><jupyter_text>Storing key-value pairs using BSTs<jupyter_code>class BSTNode():
    def __init__(self, key, value = None):
        self.key = key
        self.value = value
        self.left = None
        self.right = None
        self.parent = None<jupyter_output><empty_output><jupyter_text>let's try to relocate this BST with usernames as keys and user objects as values: ![name_tree.png](attachment:name_tree.png)<jupyter_code>BSTNode
#level 0
tree = BSTNode('jayesh.username', 'jayesh')
#view level 0
tree.key, tree.value
#level 1
tree.left = BSTNode('baban.username', 'baban')
tree.left.parent = tree
tree.right = BSTNode('sonali.username', 'sonali')
tree.right.parent = tree
#view level 1
tree.left.key, tree.left.value, tree.right.key, tree.right.value
#level 2
tree.left.left = BSTNode('akash.username','akash')
tree.left.left.parent = tree.left

tree.left.right = BSTNode('harsh.username', 'harsh')
tree.left.right.parent = tree.left

tree.right.left = BSTNode('sid.username', 'sid')
tree.right.left.parent = tree.right

tree.right.right = BSTNode('vishal.username', 'vishal')
tree.right.right.parent = tree.right
#view level 2
tree.left.left.key, tree.left.left.value, tree.left.right.key, tree.left.right.value
tree.right.left.key, tree.right.left.value, tree.right.right.key, tree.right.right.value
tree.left.left.key, tree.left.left.value, tree.left.right.key, tree.left.right.value, tree.right.left.key, tree.right.left.value, tree.right.right.key, tree.right.right.value
display_keys(tree)<jupyter_output>vishal.username
		sonali.username
				sid.username
jayesh.username
				harsh.username
		baban.username
				akash.username<jupyter_text>Insertion into BST **Question 9:** write a function to insert a new node into a BST we use the BST-property to perform insertion efficiently1. starting from the root node, we compare the key to be inserted with the current node's key2. if the key is smaller, we recurssively insert it in the left subtree(if it exists) or attach it as the left child if no left sutree exists3. if the key is larger, we recurssively insert it in the right subtree(if it exists) or attach it as the left child if no right sutree existshere's the recurssive implementation of `insert`<jupyter_code>def insert(node, key, value):
    if node is None:
        node = BSTNode(key, value)
    elif key < node.key:
        node.left = insert(node.left, key, value)
        node.left.parent = node
    elif key > node.key:
        node.right = insert(node.right, key, value)
        node.right.parent = node
    return node<jupyter_output><empty_output><jupyter_text>let's recreate out tree.![name_tree.png](attachment:name_tree.png)to create the first node, we can use this `insert` function with `None` as the target tree.<jupyter_code>tree = insert(None, 'jayesh.username', 'jayesh')
tree
display_keys(tree)<jupyter_output>jayesh.username<jupyter_text>remaining nodes can be inserted into `tree`<jupyter_code>insert(tree, 'baban.username', 'baban')
insert(tree, 'sonali.username', 'sonali')
insert(tree, 'akash.username', 'akash')
insert(tree, 'harsh.username', 'harsh')
insert(tree, 'sid.username', 'sid')
insert(tree, 'trupti.username', 'trupti')
display_keys(tree)
insert(tree, 'vishal.username', 'vishal')
display_keys(tree)<jupyter_output>vishal.username
				trupti.username
						X
		sonali.username
				sid.username
jayesh.username
				harsh.username
		baban.username
				akash.username<jupyter_text>however, that the order of the insertion of nodes change the structure of the resulting tree.<jupyter_code>tree2 = insert(None, 'akash.username', 'akash')
insert(tree2, 'baban.username', 'baban')
insert(tree2, 'harsh.username', 'harsh')
insert(tree2, 'jayesh.username', 'jayesh')
insert(tree2, 'sid.username', 'sid')
insert(tree2, 'sonali.username', 'sonali')
insert(tree2, 'vishal.username', 'vishal')
display_keys(tree2)<jupyter_output>vishal.username
										sonali.username
												X
								sid.username
										X
						jayesh.username
								X
				harsh.username
						X
		baban.username
				X
akash.username
		X<jupyter_text>It is unbalanced and skewed tree.<jupyter_code>tree_height(tree2)<jupyter_output><empty_output><jupyter_text>Finding a node in BST<jupyter_code>def find(node, key):
    if node is None:
        return None
    if key == node.key:
        return node
    if key < node.key:
        return find(node.left, key)
    if key > node.key:
        return find(node.right, key)
node = find(tree, 'harsh.username')
node.key, node.value
def find(node, value):
    if node is None:
        return None
    if value == node.value:
        return node
    if value < node.value:
        return find(node.left, value)
    if value > node.value:
        return find(node.right, value)
node = find(tree, 'sonali')
node.key, node.value
node = find(tree, 'sandesh.username')
print(node)<jupyter_output>None<jupyter_text>Updating a value in a BST**Question 10:** write a function to update the value associated with a given key within BST<jupyter_code>def update(node, key, value):
    target = find(node, key)
    if target is not None:
        target.value = value
update(tree, 'harsh.username', ('harsh', '<NAME>', '<EMAIL>'))
node = find(tree, 'harsh.username')
node.value<jupyter_output><empty_output><jupyter_text>list the nodes**Question 11:** write a function to retrieve all the key-value pairs stored in BST in the sorted order of keys.<jupyter_code>def list_all(node):
    if node is None:
        return None
    return list_all(node.left) + [(node.key, node.value)] + list_all(node.right)
#list_all(tree)<jupyter_output><empty_output><jupyter_text>Balanced Binary Trees**Question 12:** write a function to determine if a binary tree is balancedHere's a recurssive strategy:1. ensure the left subtree is balanced.2. ensure the right subtree is balanced.3. ensure the difference between heights of left subtree and right subtree is not more than 1.<jupyter_code>def is_balanced(node):
    if node is None:
        return True, 0
    balanced_l, height_l = is_balanced(node.left)
    balanced_r, height_r = is_balanced(node.right)
    balanced = balanced_l and balanced_r and abs(height_l - height_r) <= 1
    height = 1 + max(height_l, height_r)
    return balanced, height<jupyter_output><empty_output><jupyter_text>The following tree is balanced:![name_tree.png](attachment:name_tree.png)<jupyter_code>is_balanced(tree)<jupyter_output><empty_output><jupyter_text>The following tree is not balanced:![skewed_name.png](attachment:skewed_name.png)<jupyter_code>is_balanced(tree2)<jupyter_output><empty_output><jupyter_text>**Exercise:** Is the tree shown below balanced? Why or Why not? create tree and check if![new-name.png](attachment:new-name.png)<jupyter_code>n_tree = (('akash', 'baban', 'harsh'), 'jayesh', ('sid', 'sonali', ('tanya', 'vishal', None)))
n_tree1 = Tree_node.parse_tuple(n_tree)
display_keys(n_tree1)
is_balanced(n_tree1)<jupyter_output><empty_output><jupyter_text>Balanced Binary search Trees**Question 13:** write a function to create a balanced BST from a sorted list/array of key-value pairswe can use a recurssive strategy here, turning the middle element of the list into root and recurssively creating left and right subtrees<jupyter_code>def make_balanced_bst(data, lo = 0, hi = None, parent = None):
    if hi is None:
        return len(data) - 1
    if lo > hi:
        return None
    
    mid = (lo + hi) // 2
    key, value = data[mid]
    
    root = BSTNode(key, value)
    root.parent = parent
    root.left = make_balanced_bst(data, lo, mid-1, root)
    root.right = make_balanced_bst(data, mid+1, hi, root)
    
    return root
#data = [(user.username, user) for user in tree]
def balance_bst(node):
    return make_balanced_bst(list_all(node))<jupyter_output><empty_output><jupyter_text>Python friendly treemapwe are now ready to return to our original statement.**Question 1:** As a senior backend engineer, you are asked to developin a fast in-memory data structure to manage profile information (username, name and email) for 100 nillion users. it should allow the following oprations to be performed efficiently.1. **Insert** the profil information for a new user.2. **Find** the profile information of a user, given their username3. **Update** the profile information of a user, given their username.4. **List** all the users of the platform, sorted by username.we can create generic class `treemap` which supports all the operations specified in the original problem statement in a python friendly manner<jupyter_code>class Treemap():
    def __init__(self):
        self.root = None
        
    def __setitem__(self, key, value):
        node = find(self.root, key)
        if not node:
            self.root = insert(self.root, key, value)
            self.root = balance_bst(self.root)
        else:
            update(self.root, key, value)
            
    def __getitem__(self, key):
        node = find(self.root, key)
        return node.value if node else None
    
    def __iter__(self):
        return (x for x in list_all(self.root))
    
    def __len__(self):
        return tree_size(self.root)
    
    def display(self):
        return display_keys(self.root)
treemap = Treemap()
print(treemap.root)
#treemap['akash'] = 'akash'<jupyter_output><empty_output>
{'fraction_non_alphanumeric': 0.1063009001285898, 'fraction_numerical': 0.00991213030432919, 'mean_word_length': 3.5259456838021337, 'pattern_counts': {'":': 0, '<': 139, '<?xml version=': 0, '>': 142, 'https://': 0, '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': '34', 'dir': 'jupyter-structured-clean-dedup', 'id': '161142', 'license': 'Apache-2.0', 'n_tokens_mistral': 6312, 'n_tokens_neox': 6047, 'n_words': 1692, 'path': 'Binary tress, tree traversals, bst.ipynb', 'repo_name': 'MahaleVivek/Python-Data_Structure_and_Algorithms', 'size': '18673'}