### Tree - Non Linear Data structure - Used to represent the hierarchy - nodes contains parent child relationship - Root and leaf node - Children and Parent of a node - Desendents and Ancestor of a node ### Terminologies - node - root - leaf - child - parent - Node above the node - subtree - Recursive in nature since each node forms another subtree - desendents - ancestors - degree -> number of childrens it has - leaf node will have degree of zero - other other nodes are called internal nodes - internal nodes - non leaf, non root nodes ### Applications - Folders - Organixation heirachy - xml, html, json - OOPS inheritance ### Associated Data structures - Binary Search Trees - Binary Heap (Piority Queue) - represented using array - B and B+ Trees in DBMS indexes - Spanning and Shortest path trees in computer networks - Parse Tree, Expression Tree in compilers - Trie - used to support dictionaries - supports prefix search - Suffix Tree - pattern search in O(length of pattern) - Segment Trees - Binary Indexed Tree - Range Query - represented by array ### Binary Tree - every node has at-most two childrens - internally represented as linked class or with arrays ``` python class Node(): def __init__(self, val, left = None, right = None): self.val = val self.left = left self.right = right ``` #### Problems - Tree traversal - print every element in a tree atleast once - Depth first search - recursion - Inorder (left, root, right) - Preorder (root, left, right) - Postorder (left, right, root) - TC: O(n) SC: O(h) - Breath first search or level order traversal - queue - TC: O(n) SC: O(w) -> O(n) for balenced binary tree Note: level order will perfrom better when tree is speed (will no perform better when tree is balanced), DFS will perfrom better when tree is balanced ``` python # TC: O(n) # SC: O(n or height of the tree) def inorder(root): if root == None: return inorder(root.left) print(root.val, end=' ') inorder(root.right) def preorder(root): if root == None: return print(root.val, end=' ') preorder(root.left) preorder(root.right) def postorder(root): if root == None: return postorder(root.left) postorder(root.right) print(root.val, end=' ') def bfs(node): q = Queue() q.put(node) while q.qsize() > 0: t = q.get() if t is None: continue print(t.val, end=' ') q.put(t.left) q.put(t.right) print('') ``` - Height of binary tree - max distance between root to leaf - TC: O(n) SC: O(h) - size of binary tree - number of nodes - Print nodes at k distance - maximum in binary tree - print left view of binary tree - children sum property - check for balanced binary tree - max width of binary tree - convert binary tree to doubily linked list - construct binary tree from inorder and preorder - tree traversal in spiral form - diameter of a binary tree - lca of binary tree - burn a binary tree from a leaf - count nodes in a complete binary tree - serialize and deserilize a binary tree - iterative - inorder - preorder - postorder traversal #### cses problems - subtree sum - tree matching - tree dp problem - tree diameter - 2d fs - dynamic programming - tree distance 1 - max diameter - tree distance 1 - rerouting dp on tree - company queries I - binary lifting, lca - company queries II - lca - distance queries - lca, level order of traver - counting path - pending 297. Serialize and Deserialize Binary Tr https://leetcode.com/problems/binary-search-tree-iterator/solution/