<jupyter_start><jupyter_text><jupyter_code>class Node():
    def __init__(self, key):
        self.value = key
        self.left = None
        self.right = None
# create root
root = Node(1)
''' following is the tree after above statement
        1
      /   \
     None  None'''
 
root.left      = Node(2);
root.right     = Node(3);
   
''' 2 and 3 become left and right children of 1
           1
         /   \
        2      3
     /    \    /  \
   None None None None'''
 
 
root.left.left  = Node(4);
'''4 becomes left child of 2
           1
       /       \
      2          3
    /   \       /  \
   4    None  None  None
  /  \
None None'''<jupyter_output><empty_output><jupyter_text>Properties1. **The maximum number of nodes at level ‘l’ of a binary tree is 2l.** Here level is the number of nodes on the path from the root to the node (including root and node). Level of the root is 0. 2. **The Maximum number of nodes in a binary tree of height ‘h’ is 2h+1 – 1.**3. **In a Binary Tree with N nodes, minimum possible height or the minimum number of levels is Log2(N+1) - 1**4. **A Binary Tree with L leaves has at least | Log2L? |+ 1   levels**  Types1. **Full Binary Tree** A Binary Tree is a full binary tree if every node has 0 or 2 children.2. **Complete Binary Tree**: A Binary Tree is a Complete Binary Tree if all the levels are completely filled except possibly the last level and the last level has all keys as left as possible 3. **Perfect Binary Tree** A Binary tree is a Perfect Binary Tree in which all the internal nodes have two children and all leaf nodes are at the same level.4. **Balanced Binary Tree** A binary tree is balanced if the height of the tree is O(Log n) where n is the number of nodes. For Example, the AVL tree maintains O(Log n) height by making sure that the difference between the heights of the left and right subtrees is at most 1. Red-Black trees maintain O(Log n) height by making sure that the number of Black nodes on every root to leaf paths is the same and there are no adjacent red nodes. Balanced Binary Search trees are performance-wise good as they provide O(log n) time for search, insert and delete.5. A degenerate (or pathological) tree A Tree where every internal node has one child. Such trees are performance-wise same as linked list.6. In a k-ary tree where every node has either 0 or k children, following property is always true.   L = (k - 1)*I + 1Where L = Number of leaf nodes,      I = Number of internal nodes  7. In Binary tree, a number of leaf nodes is always one more than nodes with two children.      L = T + 1Where L = Number of leaf nodes,    T = Number of internal nodes with two children  Enumeration of Binary TreesA Binary Tree is labelled if every node is assigned a label and a Binary Tree is unlabelled if nodes are not assigned any label.For example, let T(n) be count for n nodes.$T(0) = 1$  [There is only 1 empty tree]$T(1) = 1$$T(2) = 2$$T(3) =  T(0)*T(2) + T(1)*T(1) + T(2)*T(0)$ = 1*2 + 1*1 + 2*1 = 5$T(4) =  T(0)*T(3) + T(1)*T(2) + T(2)*T(1) + T(3)*T(0)$     =  1*5 + 1*2 + 2*1 + 5*1     =  14 The above pattern basically represents n’th Catalan Numbers. First few catalan numbers are 1 1 2 5 14 42 132 429 1430 4862,…  ![image.png](data:image/png;base64,iVBORw0KGgoAAAANSUhEUgAAAsgAAAAoCAYAAADjcAzdAAARzklEQVR4nO2d4XGrvBKGXcB3BzogHZAOcAe4A9wB6QB3QDpQOiAdyB2oBEpQCXt/5CzBWBKSECCcfWaYOccONhbS7qvdlTj999//gA466KCDDjrooIMOOuj4OU5AEARBEJEjhIDv72/4+PiANE2haZq9L4kgiBeGBDJBEAQRPYwx4JyDlBJOpxMJZIIgVoUEMkEQBHEoSCATBLE2JJBfiL7voe/7h9eEEE+vEQRBhEAIAVLKh9cwyrsmJJAJglib1QVySHF2NKEnpYT7/R78EEI8fVfXddA0DeR5Doyx4f9d10FVVXC9XndogW1QtcerEdNvPNo4XMLRfmvf96vYHFU7NE0DbdtClmXQ9z20bQt1XQPnfLBDaxGjQHbtK1LKaPpXTNdCPEP3Zh9WFciMMaiqKtjnCSGgLMvVoxOh6LoOTqcTnE4nyLIMiqJwPvD88ZGm6dN3lWUJAAB1XUOaptC27fAe5xxOp9NLDjLGGNR1vfdlrE7TNKsKDhuklFAURVRifW0YY9EJMRN1XQ92Is9zZ3uT57nS5kztOApiAIAsyyDLsod+0TQNvL+/r/Y7YxPIvr6uqqrdx5OU8lB+9S8SWkvFhCnjtHefPHHO4Xa7eR86MIoQ+gd2XTeIwSNQVdUgan3bQggxRGrQYXVdN7wvpRycFTrFMSjU9+psXdet0se6rnv6rUfFZvJSFMXDfdfRNI13W3POF3//q1FV1e6TE1uklIOduFwu3p/DOYe6riFJEqX96roO+r4fFsyNJ+QAP0J9zbHpI5DXskPo63ywnXT2fb/o2nWfL6WE9/f33UX6X0dKOeuf67p+GmdHRAgB1+sV0jSFoiigqqphcj72L1VV7e5vTnmeQ5IkUNf1sEqYc/4Q/Wzbdnidcw5N0wyGUwUa6bUGXV3XUUUPTIwd1vl8Xvx5bdtCkiTK2SQ6q6kzr+sasixb/N2+YIRp2scYY7N9LEkS5Wf2fQ9Zls0aFc45pGkadZS5bVtI09QoTgF+7m+e50YxjW1aFAU0TfPQpmVZDpHF8euMseE93biq6zrqNgxBnufK7Ay2+9z9iQUhxMO4WoKUcohKqyYJusk3jvfpdblEs00RMx+BnGWZ0tfZ2CGdr0M7NDfBNdkhIcSsLcN7UFXV0zVi1L8sy4fX27YdspC6vluW5UuILh1930OapkF871pg37Dpz0eyQ1P6vofL5QJJkkDTNE/9XUo59G/s77tHkHUDE9PyOoHSdZ121lxV1aoCVkoJSZIcpmQgpMPCz0uS5Om+obOatovKWW2FEEKbScDr1Yl3U4TY1rC3bQun0yk6cdc0DZzPZ8AJqsmJjWnb1hgZNLULOkvd+9MZPNL3vbK/vRI4RnU2jTG2aslAaLDfn06nIIGKtm2VIkM1+ca2XDP64yqQ17JDtr5uzg7NfU6WZVr7MGc/kiRR9gHO+a6Bky1AHRNbppExBpfLBfI8HyY4Nv3oqPcMJwFzAR6AXz/lm5UJyUk3qJqmGWalOlSdru/7Tepdq6o6VE1OaIelqklVOSs0EPidW0cLcNGO7j1VfSPCOVe+xzl3Emwxpg8558MYmYvyjMHJoepvMV2rY67/1XWtfK8sy0ONNV9UOzKMybLsMKUWAL/96v39PcjkpiiKJ7ue5/lT3xjbob7vVxHKrgJ5LTvkEuUy2SGT3xRCaK9tHHzRobMJWZa9dPQYidH+j3eXQq1l25+Pdt8wQ2NbcosT1hiCWtpRNRdtEkIob+hWwhUNw5GiWtimb29vQa57em9Uzgp3tgD46Xhb1/SYBBvOnHWiA1OcU15NsLkIZIAfh66auDLGjG1pygjhdUzZasJ7BNq2PVQUGSdTp9MpyC42QointQ+qSHFRFINzq+t6FRvtKpBNgR5fOxTa1+V5rvyeuq614w8DLyY7GyLIQKyHq0BmjMHb29u6FxUIIQSkaerU19Dn7F1/DGAQyHPRJqzdmpIkyWZRliRJDjWTCu2wpqiMPKZkvr6+Np+RdV2n7QvoXE3iq+u6J9GI5x21DkuFq0DW1X2anLVNRkh1ftu2UaS6YgAn5TFGpHTgxMgkAJd+9rQf1nUNl8sFbrdb0O/k/xaUn8/nIdDw8fFhXECH561hh9I0DerEm6ZRCh/TmJ1bO6A7HxdGEfvjKpBRQMZuh6SU8Pb25mV7Ygl+KgWyTbRJteoSz5uLNnVdB19fXw/n457BphW3U8qyPNwgX9Nh6dpN9QCRLcBV7irm6v4A1H3MdkeOvu/h8/MzeiMC4C6QdZE70z2eywjpzp9bLIXnqcatEAK+vr6exnpMSCmHa7Qh1DqCLcESgjRNg9sB3efNlatsiWmHAF87ZOvrXOyQ7jNN32GzfkF1Pi6UMiGEgM/Pz6fzOefw+fkJ39/f0dzjKTiuv7+/976UWVwFMoDd/dsb/F0+NdOxBGWUAtkm2qQ7zySq8W+6roO6rofaONzjD2fqeZ5bRVibplGuOo+dNR3WUZir+zOdNzfg8OEouDo8hlSNCVeBDPBjQFwyAr717zaiGus7kySBruseViPjanrdQqE9wevEGk+ble5FURxqm0kEywiOVCKyBb52yMbX+dghl8CJTf2xCoxAmuwN+micQAghhucQMMaGEstQ5YIhwfGMCzOPIiRdS4ZiDw7i5O1oAYUxypFlE21SMXfT+r4fDBHOlq/X65NBGA9KE7az+DFCiEX7Sc7tFWvLX3dYc3V/OnALKB246T2CD2iJGR+BPNcOY2wyQqbzTNdVVdXgIIuigPf394fXkDzPoxOW49pOdFJzVFXlPGaX7r97u90WT6RxJ5JYFr/EQmx2yEUo2dQfq7Dxm+NrP51+tihV9RtXYbcF42vH/XVjxkcg+wQHt7RD422CjxwEVHoE32jTnNHAiBL+W9cp8L05wWDjwKfgzHfJESIS9pcdlk3dn44sy4xCa9zHMFIS+4I+X4Fsu1DDNyNkM76mjlS3GCNJkqgmKuPJOgAM2+3NYSukx+Bj35ccIaJ04/1+X6mG35cldsjG12HE2MUOuUx8beqPVcz1YcwK4b91aXJsv5gE8njdC15fbBPzKb4COWY7hJmZI25JN+aphX2jTQB2RgPBwa1qcGxc2wjyUY39X3VYNnV/OuYMyfg92360Nz4C2cVA+maE5jI5WB4F8JvuVU32YnRUnPPhd5mufYqPY4qJEE/2fBWW2KG5ibqvHXIRyC77p0+vzdSHhRDDZ6KPUkXY0f/GJJAZY0O/Nl17TGwlkLcEfU5MQREfnlrYN9oE4FY4booo4ZPX5ji6QAb4dVixp4FC4lv3B+CW0rPtR2Nw4uZz+BqDtQWyb0bI5TtMWR8fR4XjwudwvecuAiZ2xzTH+MmeMQmbPYjRDtkKZN/6YwC3PozjcEkgawzaOp/DVZMUReG8lR3+pi3sDuIjkNGmxgreZ1cbI6WMSs89tbBvtAnPtTE2poiNSzrqFQQyLm6KPcoZEt+6PwB7x4TRoSMsEFhTIC/JCNnuGALwO7FQgU421lq0JEmsJ6hHF8gAv3uj//UI8hI7lGXZKnbIViD71h8DuPVhk7j3CUBsxVHK6wBeO4LsKpAZY1Etqn9qYd9oE4D74FY1hOm9Kb41yDEs0gP43ScwdAqoaZpVDAM+S32J6FxS9wdgv3tD7KJsjI9ALsvSyjktyQi5jC9TRshFgG6Nq4DxcUyMsd0X6SFrTMillHA+n4PaMSklfHx8QNM0UNf1sCtByM9fYodsfZ2rHbL9XN/6YwD7PowiU2VvXcqS9gB/4xGCZ1vWIG9lh3yzM6q+zxiDz8/PYUKP+6GPX1uLhxZeEm0CsN96xFR/PJ2VNoZFcb67WCwtVA9lqIvRE6dCUlVVUGeF2/D5DOQpS+r+AOwciKrmNeZIwpq7WCzJCKETnLsu/DtVv5iWV0gpo3KqU1vEGDP+3rquncV+LIv0+r6HNE2DiwZ8xHlIAVsUxUOfxdKQUN8Rqx2yLVP0rT8GsPebOHZVwappeYUQIqps3VRHrPVExxD4CmTXvrulHcLJlcsT/5qmeerPbdsO2/bVdQ11XQ++ZIsnmz4IZLxRvotpmsZu6xFdREk1K51bCOEr5vfmqE8yWiqQl9T94flzgwKd31iUvZpAzrLMSmguyQjh+XOOz1R/rBKgUaXQJvZuzvYVB90HWUoJ7+/vUYkYHbr6yrqurfaqtmGpHbLxda52CAX1XHBjSf0xgN0+yADm6LdKgMaSrVPpiJjtv49AdlnMuRc4xmyCdYwx5d/hPcS+OPZjPgFSV4YRNn4soG+Ex+aCTakZfA8d6HirHBVlWR7SWTHGIMuyaGe0JpYI5L7vhz7m+xk2dbHoYPFvqqqKxnhPQeHiEuXVPUlvCgpX2zpiFTbrCkwZobIsh8lwjBOVcV/Eh5rM/f0RROaUqqqia3sdukwkjusQe0IvtUPo62zsEDr1OTtk6/BRLCyJnmVZNtuP5+qP0fcKIaLKCk1Lw8Zbf8YI2k+XNjzCk/SklJDnuTFrhdttqsRx3/fD2FEFhLZYqHjK83yYjUyPPM+d04lJkhhnDChwdA2GT7T6+PiYnXkkSXI4ZyWEWG1RXtu2DymINXB1KlVVwVwfc5nk2IhDHJjX6zV4uUkoMIOgO0z9WueccW9t0+cmSeLkLGzSWKZ7iE8Ru91uygeI7E3TNFAUxVDvagIn8LFOtnS0bbvKojwpJbRtG7w+WPdQjSWLsm3skOsEAp8cqcPVDunS5pzzoU10h2u/rKpq1u6abD0GeW63G5RlGd24rqoKLpcLNE3zcvYfMwBHWdiPmf7z+Qy32w3u9zvcbje4XC5WwStdxmOLpwkGl982A29uMNkMdJsZfGxIKSFN0yAp5umDDrA2WtUuPouEdINvaYlFCGyjYUcTMrZsGQ1E42RqS5sxGPO9kFJa/QYU00ei6zpIkiRI+0/LY3DCo2qXpmmcbQ6i250htn13Q9uhPM83C/jY+M+jj+uYr20JOOE9Gpihw1pjW+02zQgD/AbKcLysda+DC2R0qGsL1yOlDJGQz4Uvy/LBWWH6gTH2VJeNwtnl0N2/GBwUrsQ/0uQoFGgYtkwZ4gLNv85cdiw2hBCQpmmQSBNGQxHO+dAWqlI3V3sz7s9HEciYDQxhh9CmbSnq8jw/VH8mfsiy7E/dN8z+jBmL5jUXfq9SwFHX9apGDFPJRxJINpF1l88ap+KklINh9UkVuhCLgyrLMorr2JqmaTavuz/ieAsNY+xQ0WOsbQ/hSPGzxnYF7Q0GREI67DmBHFNZXajJ4x6TUCzdII5D13WHjB4vQbXn+Dhr1bbtcSLIAL9b8qx10WVZRmUk5whVA8g5HxZ0mRY5rhldjEUg931/2IWOvuBv3iN12Pzbj/YvgguYj1LzB/BjI0NMlBljkKaptu5/jZ2EsFZ4ypIa5LUI4es457uJnqqqDuVL/zJoh2Lq/1uQ5/nT+Or7HsqyhLquV90VabUlgEKIVQY9Lgo5Cpg6c3GunHO43+9wv9/h6+sLPj4+BmFs2rZrHFkWQgzisW1bOJ/P1sflcom6BhnhnB9yFxNf8jzf1ThOy3r+CmVZHiql2fx7Up4tUsrB3tzvd/j8/ITr9Trs9GDaG3+8unzcN3Gxte1xvV6Hc9fexSI0Qgjv7ELo/Z19vr8IvIc1sQ5Hs0OvwKp7ZHRdFzTqhBtGHwXcmH8sbEMcurTYeFeP8cbor1aDPAYfYvLqxLAbh5QSyrL8U860bdvd290F3CUo9KEaY5ixwv4wtvVLapB1WznGvHc8Y8zL18UwnlAk/6Vs3NFo25Yi/Tuw+sO8Q872Y4sczCGl9HIUc4fOoOIWXms81UgIAd/f33A6neByucD9fo/GoB6tX/gQ02+M6VrW5mi/te/7VWyOqh34v5IHAPMTT30oy/IhqozbBe4tJk249pXx2pG9ielaiGfo3uzD6gKZ2A7O+Sr7IHPOtY+eJAji74J7r48jwKHAund8zGzM4pggiNeDBDJBEARBEARBjCCBTBAEQRAEQRAjSCATBEEQBEEQxAgSyARBEARBEAQxggQyQRAEQRAEQYwggUwQBEEQBEEQI0ggEwRBEARBEMSI/wMw55svUc7GDQAAAABJRU5ErkJggg==) Here, T(i-1) represents number of nodes on the left-sub-tree T(n−i-1) represents number of nodes on the right-sub-treen’th Catalan Number can also be evaluated using direct formula.    $T(n) = \frac{(2n)!}{(n+1)!n!}$ How many labelled Binary Trees can be there with n nodes? To count labelled trees, we can use above count for unlabelled trees. The idea is simple, every unlabelled tree with n nodes can create n! different labelled trees by assigning different permutations of labels to all nodes. Therefore,     Number of Labelled Trees = (Number of unlabelled trees) * n!  Applications of tree data structure  Tree Traversal![image](https://media.geeksforgeeks.org/wp-content/cdn-uploads/2009/06/tree12.gif)Depth First Traversals: 1. Inorder (Left, Root, Right) : 4 2 5 1 3 2. Preorder (Root, Left, Right) : 1 2 4 5 3 3. Postorder (Left, Right, Root) : 4 5 2 3 1Breadth First or Level Order Traversal : 1 2 3 4 5  1.    Extra Space required for Level Order Traversal is O(w) where w is maximum width of Binary Tree. In level order traversal, queue one by one stores nodes of different level.2.    Extra Space required for Depth First Traversals is O(h) where h is maximum height of Binary Tree. In Depth First Traversals, stack (or function call stack) stores all ancestors of a node.*Extra space required for Level order traversal is likely to be more when tree is more balanced and extra space for Depth First Traversal is likely to be more when tree is less balanced.*<jupyter_code># Inorder Traversal
def print_inorder(root):
    if root:
        print_inorder(root.left)
        print(root.value, end=' ')
        print_inorder(root.right)
# Preorder Traversal
def print_preorder(root):
    if root:
        print(root.value, end=' ')
        print_preorder(root.left)
        print_preorder(root.right)
# Postorder Traversal
def print_postorder(root):
    if root:
        print_postorder(root.left)
        print_postorder(root.right)
        print(root.value, end=' ')
root = Node(1)
root.left = Node(2)
root.right = Node(3)
root.left.left = Node(4)
root.left.right = Node(5)
print('Inorder traversal: ', end=' ')
print_inorder(root)
print()
print('Preorder traversal: ', end=' ')
print_preorder(root)
print()
print('Postorder traversal: ', end=' ')
print_postorder(root)
# Level Order Traversal
def printLevelOrder(root):
    h = height(root)
    for i in range(1, h+1):
        printCurrentLevel(root, i)


def printCurrentLevel(root, level):
    if root is None:
        return
    if level == 1:
        print(root.value, end=' ')
    elif level > 1:
        printCurrentLevel(root.left, level - 1)
        printCurrentLevel(root.right, level - 1)


def height(node):
    if node is None:
        return 0
    else:
        lheight = height(node.left)
        rheight = height(node.right)
        if lheight > rheight:
            return lheight + 1
        else:
            return rheight + 1
print('Level Order Traversal: ', end=' ')
printLevelOrder(root)<jupyter_output>Level Order Traversal:  1 2 3 4 5<jupyter_text>Level Order Using QueueprintLevelorder(tree)1. Create an empty queue q2. temp_node = root /*start from root*/3. Loop while temp_node is not NULL        a. print temp_node->data.        b. Enqueue temp_node’s children (first left then right children) to q        c. Dequeue a node from q.<jupyter_code>def printLevelOrder(root):
    # Base Case
    if root is None:
        return
     
    # Create an empty queue
    # for level order traversal
    queue = []
 
    # Enqueue Root and initialize height
    queue.append(root)
 
    while(len(queue) > 0):
       
        # Print front of queue and
        # remove it from queue
        print(queue[0].value, end=' ')
        node = queue.pop(0)
 
        #Enqueue left child
        if node.left is not None:
            queue.append(node.left)
 
        # Enqueue right child
        if node.right is not None:
            queue.append(node.right)
print('Level Order Traversal: ', end=' ')
printLevelOrder(root)<jupyter_output>Level Order Traversal:  1 2 3 4 5<jupyter_text>Time Complexity: O(n) Let us see different corner cases. Complexity function T(n) — for all problem where tree traversal is involved — can be defined as:T(n) = T(k) + T(n – k – 1) + cWhere k is the number of nodes on one side of root and n-k-1 on the other side.Let’s do an analysis of boundary conditionsCase 1: Skewed tree (One of the subtrees is empty and other subtree is non-empty )k is 0 in this case. T(n) = T(0) + T(n-1) + c T(n) = 2T(0) + T(n-2) + 2c T(n) = 3T(0) + T(n-3) + 3c T(n) = 4T(0) + T(n-4) + 4c………………………………………… …………………………………………. T(n) = (n-1)T(0) + T(1) + (n-1)c T(n) = nT(0) + (n)cValue of T(0) will be some constant say d. (traversing a empty tree will take some constants time)T(n) = n(c+d) T(n) = Θ(n) (Theta of n)Case 2: Both left and right subtrees have equal number of nodes.T(n) = 2T(|_n/2_|) + cThis recursive function is in the standard form (T(n) = aT(n/b) + (-)(n) ) for master method Master Theorem. If we solve it by master method we get (-)(n)Auxiliary Space : If we don’t consider size of stack for function calls then O(1) otherwise O(h) where h is the height of the tree. The height of the skewed tree is n (no. of elements) so the worst space complexity is O(n) and height is (Log n) for balanced tree so the best space complexity is O(Log n).  Write a Program to print the size of the tree<jupyter_code>def size(node):
    if node is None:
        return 0
    return size(node.left) + 1 + size(node.right)
print(f'Size of the tree is: {size(root)}')<jupyter_output>Size of the tree is: 5<jupyter_text>Write a Program to find the maximum or minimum element of a tree.<jupyter_code>def find_max(root):
    # Base Case
    if root is None:
        return float('-inf')

    max_ = root.value
    lmax_ = find_max(root.left)
    rmax_ = find_max(root.right)
    if lmax_ > max_:
        max_ = lmax_
    if rmax_ > max_:
        max_ = rmax_
    return max_
root = Node(2)
root.left = Node(7)
root.right = Node(5)
root.left.right = Node(6)
root.left.right.left = Node(1)
root.left.right.right = Node(11)
root.right.right = Node(9)
root.right.right.left = Node(4)
print('Inorder traversal: ', end=' ')
print_inorder(root)
print()
print('Preorder traversal: ', end=' ')
print_preorder(root)
print()
print('Postorder traversal: ', end=' ')
print_postorder(root)
print(f'The Maximum value in the tree is {find_max(root)}.')<jupyter_output>The Maximum value in the tree is 11.<jupyter_text>Print left view of a Binary TreeLeft view of a Binary Tree is set of nodes visible when tree is visited from left side. Method-1 (Using Recursion)The left view contains all nodes that are first nodes in their levels. A simple solution is to do level order traversal and print the first node in every level.<jupyter_code>def left_view(root):
    max_level = [0]
    left_view_util(root, 1, max_level)


def left_view_util(root, level, max_level):
    if root is None:
        return
    if max_level[0] < level:
        print(root.value, end=' ')
        max_level[0] = level
    left_view_util(root.left, level + 1, max_level)
    left_view_util(root.right, level + 1, max_level)
left_view(root)<jupyter_output>2 7 6 1<jupyter_text>Method-2 (Using Queue):In this method, level order traversal based solution is discussed. If we observe carefully, we will see that our main task is to print the left most node of every level. So, we will do a level order traversal on the tree and print the leftmost node at every level.<jupyter_code>def left_view(root):
    if root is None:
        return

    queue = []
    queue.append(root)
    while len(queue) > 0:
        n = len(queue)
        for i in range(1, n + 1):
            temp = queue[0]
            queue.pop(0)
            if i == 1:
                print(temp.value, end=' ')
            if temp.left is not None:
                queue.append(temp.left)
            if temp.right is not None:
                queue.append(temp.right)
left_view(root)
root1 = Node(10)
root1.left = Node(2)
root1.right = Node(3)
root1.left.left = Node(7)
root1.left.right = Node(8)
root1.right.right = Node(15)
root1.right.left = Node(12)
root1.right.right.left = Node(14)
left_view(root1)<jupyter_output>10 2 7 14<jupyter_text>Diameter of a TreeThe diameter of a tree (sometimes called the width) is the number of nodes on the longest path between two end nodes.![image](https://media.geeksforgeeks.org/wp-content/uploads/Diameter-of-Binary-Tree.png)The diameter of a tree T is the largest of the following quantities:*    the diameter of T’s left subtree.*    the diameter of T’s right subtree.*    the longest path between leaves that goes through the root of T (this can be computed from the heights of the subtrees of T)<jupyter_code>def height(node):
    if node is None:
        return 0
    return 1 + max(height(node.left), height(node.right))


def diameter(root):
    if root is None:
        return 0

    lheight = height(root.left)
    rheight = height(root.right)

    ldiameter = diameter(root.left)
    rdiameter = diameter(root.right)

    return max(lheight+rheight+1, max(ldiameter, rdiameter))
print(diameter(root))<jupyter_output>7<jupyter_text>**Time Complexity: O(n2)**The above implementation can be optimized by calculating the height in the same recursion rather than calling a height() separately. This  optimization reduces time complexity to O(n).<jupyter_code>class Height:
    def __init(self):
        self.h = 0


def diameterOpt(root, height):
 
    # to store height of left and right subtree
    lh = Height()
    rh = Height()
 
    # base condition- when binary tree is empty
    if root is None:
        height.h = 0
        return 0
 
     
    # ldiameter --> diameter of left subtree
    # rdiamter  --> diameter of right subtree
     
    # height of left subtree and right subtree is obtained from lh and rh
    # and returned value of function is stored in ldiameter and rdiameter
     
    ldiameter = diameterOpt(root.left, lh)
    rdiameter = diameterOpt(root.right, rh)
 
    # height of tree will be max of left subtree
    # height and right subtree height plus1
 
    height.h = max(lh.h, rh.h) + 1
 
    # return maximum of the following
    # 1)left diameter
    # 2)right diameter
    # 3)left height + right height + 1
    return max(lh.h + rh.h + 1, max(ldiameter, rdiameter))
 
# function to calculate diameter of binary tree
def diameter(root):
    height = Height()
    return diameterOpt(root, height)
print(diameter(root))<jupyter_output>7<jupyter_text>Inorder Tree Traversal without RecursionUsing Stack is the obvious way to traverse tree without recursion. Below is an algorithm for traversing binary tree using stack.1. Create an empty stack S.2. Initialize current node as root3. Push the current node to S and set current = current->left until current is NULL4. If current is NULL and stack is not empty then           a. Pop the top item from stack.          b. Print the popped item, set current = popped_item->right           c. Go to step 3.5. If current is NULL and stack is empty then we are done.> **Time Complexity:** $O(n)$<jupyter_code>def in_order(root):
    stack = []
    current = root
    while True:
        if current is not None:
            stack.append(current)
            current = current.left
        elif stack:
            current = stack.pop()
            print(current.value, end=' ')
            current = current.right
        else: 
            break
    print()
in_order(root)<jupyter_output>7 1 6 11 2 5 4 9<jupyter_text>Write a Program to Find the Maximum Depth or Height of a TreeAlgorithm:  maxDepth()1. If tree is empty then return 02. Else     (a) Get the max depth of left subtree recursively  i.e.,           call maxDepth( tree->left-subtree)     (a) Get the max depth of right subtree recursively  i.e.,           call maxDepth( tree->right-subtree)     (c) Get the max of max depths of left and right           subtrees and add 1 to it for the current node.         max_depth = max(max dept of left subtree,                               max depth of right subtree)                              + 1     (d) Return max_depth<jupyter_code>def max_depth(node):
    if node is None:
        return 0
    else:
        left_depth = max_depth(node.left)
        right_depth = max_depth(node.right)
        max_depth_ = max(left_depth, right_depth) + 1
    return max_depth_
max_depth(root)<jupyter_output><empty_output><jupyter_text>If you are given two traversal sequences, can you construct the binary tree?It depends on what traversals are given. If one of the traversal methods is Inorder then the tree can be constructed, otherwise not. Therefore, following combination can uniquely identify a tree.1. Inorder and Preorder.2. Inorder and Postorder.3. Inorder and Level-order.And following do not.1. Postorder and Preorder.2. Preorder and Level-order.3. Postorder and Level-order.<jupyter_code><jupyter_output><empty_output>
{'fraction_non_alphanumeric': 0.07721886876816454, 'fraction_numerical': 0.0587078023697742, 'mean_word_length': 4.449805068226121, 'pattern_counts': {'":': 0, '<': 41, '<?xml version=': 0, '>': 54, 'https://': 2, 'lorem ipsum': 0, 'www.': 0, 'xml': 0}, 'pii_count': 0, 'substrings_counts': 0, 'word_list_counts': {'cursed_substrings.json': 3, 'profanity_word_list.json': 0, 'sexual_word_list.json': 0, 'zh_pornsignals.json': 0}}
{'chain_length': '12', 'dir': 'jupyter-structured-clean-dedup', 'id': '285382', 'license': 'MIT', 'n_tokens_mistral': 10239, 'n_tokens_neox': 9503, 'n_words': 2057, 'path': 'Tree_Data_Structure.ipynb', 'repo_name': 'Yasir323/Data-Structures-and-Algorithms-in-Python', 'size': '22365'}