<jupyter_start><jupyter_text>CC189 - Cracking the Coding Interview Chapter 4 Trees and Graphs  Binary Tree* In-order: left, current, right* Pre-order: current, left, right* Post-order: left, right, current* Insert node: insert value by comparing to the root and deciding which way to go Search* DFS* BFS Referencehttps://github.com/buy/cc150https://github.com/kdn251/interviews/tree/master/CrackingTheCodingInterview<jupyter_code># Tree with defaultdict
# from collections import defaultdict

# def tree():
#     return defaultdict(tree)

# users = tree()

# users['cindy']['username'] = 'cindy.lxr'

# def add(t, path):
#     for node in path:
#         t = t[node]

# add(users, ['left', 'right'])<jupyter_output><empty_output><jupyter_text>Implementation of a Tree Node<jupyter_code>from collections import defaultdict
class Node:
    def __init__(self,data):
        self.data = data
        self.children = defaultdict(Node)<jupyter_output><empty_output><jupyter_text>Implementation of a Binary Tree<jupyter_code>class Node:
    def __init__(self, data):
        self.data = data
        self.left = None
        self.right = None

    def add_left(self, data):
        self.left = Node(data)

    def add_right(self, data):
        self.right = Node(data)
node1 = Node(3)

node1.add_left(2)
node1.add_right(5)

node1.left.add_left(1)<jupyter_output><empty_output><jupyter_text>Binary Tree with defaultdict<jupyter_code>def inOrderTraverse(n):
    if BT[n]:
        if BT[n]['left']:
            inOrderTraverse(BT[n]['left'])
        print(n)
        if BT[n]['right']:
            inOrderTraverse(BT[n]['right'])
BT = defaultdict(lambda: {'left': None, 'right': None})
BT[10]['left'] = 5
BT[5]['left'] = 3
BT[5]['right'] = 7
BT[10]['right'] = 20
BT[20]['right'] = 30
inOrderTraverse(10)
def preOrderTraverse(n):
    if BT[n]:
        print(n)
        if BT[n]['left']:
            preOrderTraverse(BT[n]['left'])
        if BT[n]['right']:
            preOrderTraverse(BT[n]['right'])
preOrderTraverse(10)<jupyter_output>10
5
3
7
20
30<jupyter_text>Binary Tree Traversal<jupyter_code>def inOrderTraverse(node):
    if node:
        inOrderTraverse(node.left)
        print(node.data)
        inOrderTraverse(node.right)
inOrderTraverse(node1)
def preOrderTraverse(node):
    if node:
        print(node.data)
        preOrderTraverse(node.left)
        preOrderTraverse(node.right)
preOrderTraverse(node1)
def postOrderTraverse(node):
    if node:
        postOrderTraverse(node.left)
        postOrderTraverse(node.right)
        print(node.data)
postOrderTraverse(node1)<jupyter_output>1
2
5
3<jupyter_text>Implementation of an Adjacency List<jupyter_code>class Node:
    def __int__(self, data):
        self.data = data
        self.children = defaultdict(Node)

class Graph:
    def __int__(self):
        self.nodes = []
    def addNode(self, node):
        self.nodes.append(node)<jupyter_output><empty_output><jupyter_text>Implementation of an Adjacency Matrix<jupyter_code>adjacencyMatrix = defaultdict(lambda: defaultdict(bool))
for (k, v) in [
    (1, 3),
    (2, 3),
    (1, 6),
    (6, 2)
]:
    adjacencyMatrix[k][v] = True
    adjacencyMatrix[v][k] = True
adjacencyMatrix[2]
adjacencyMatrix[0][1]<jupyter_output><empty_output><jupyter_text>4.1 Route Between Nodes<jupyter_code>from collections import deque
def hasRoute(adjacencyMatrix, a, b):
    visited = defaultdict(bool)
    visited[a] = True
    q = deque()
    q.append(a)
    while len(q) > 0:
        r = q.popleft()
        if r == b:
            return True
        for n in adjacencyMatrix[r].keys():
            if not visited[n]:
                visited[n] = True
                q.append(n)
    return False
adjacencyMatrix = defaultdict(lambda: defaultdict(bool))
for (k, v) in [
    (0, 1),
    (0, 5),
    (0, 4),
    (1, 3),
    (1, 4),
    (2, 1),
    (3, 2),
    (3, 4)
]:
    adjacencyMatrix[k][v] = True<jupyter_output><empty_output><jupyter_text>```5  1 <-- 2         ↘  ↓  ↘  ↑            4 <-- 3```<jupyter_code>for (a, b) in [
    (2, 5),
    (0, 5),
    (5, 0),
    (4, 5),
    (0, 3),
    (3, 0)
]:
    print("({}, {}) => {}".format(a, b, hasRoute(adjacencyMatrix, a, b)))<jupyter_output>(2, 5) => False
(0, 5) => True
(5, 0) => False
(4, 5) => False
(0, 3) => True
(3, 0) => False<jupyter_text>4.2 Minimal Tree<jupyter_code>mylist = [n for n in range(4, 17)]
mylist
def minBST(mylist):
    def createMinBST(mylist, start, end):
        if end < start:
            return None
        mid = (start + end) // 2
        
3//2<jupyter_output><empty_output><jupyter_text>4.3 List of Depths  4.4 Check Balanced  Define a binary tree<jupyter_code>class Node(object):
    def __init__(self, data=None):
        self.data = data
        self.left = None
        self.right = None

    def add_left(self, data):
        self.left = Node(data)
        
    def add_right(self, data):
        self.right = Node(data)
def getHeight(node):
    if node is None:
        return 0
    return 1 + max(getHeight(node.left), getHeight(node.right))

def isBalanced(node):
    if node is None:
        return True
    if abs(getHeight(node.left) - getHeight(node.right)) > 1:
        return False
    return isBalanced(node.left) and isBalanced(node.right)
root = Node('root')
root.left = Node("left")
root.right = Node("right")
root.left.left = Node("left 2")
root.left.right = Node("left-right")
getHeight(root)
isBalanced(root)<jupyter_output><empty_output><jupyter_text>Kr Tree<jupyter_code>inputList = [[1,4], [1,5], [2,5], [3,6], [6,7]]
class Tree:
    def __init__(self, root=None):
        self.nodes = [root]
        
class Node:
    def __init__(self, data=None):
        self.data = data
        self.left = None
        self.right = None

    def add_left(self, data):
        self.left = Node(data)

    def add_right(self, data):
        self.right = Node(data)
myTree = Tree()
def Node(data=None):
    return {
        "data": data,
        "children": defaultdict(Node)
    }
myNode = Node(3)
myNode['children'][1] = 5
myTree = Tree()
inputDict<jupyter_output><empty_output>
{'fraction_non_alphanumeric': 0.14481054365733115, 'fraction_numerical': 0.023228995057660625, 'mean_word_length': 3.152530779753762, 'pattern_counts': {'":': 2, '<': 49, '<?xml version=': 0, '>': 55, 'https://': 2, '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': '12', 'dir': 'jupyter-structured-clean-dedup', 'id': '203682', 'license': 'MIT', 'n_tokens_mistral': 2272, 'n_tokens_neox': 2191, 'n_words': 492, 'path': 'cc189/4.Trees_and_Graphs.ipynb', 'repo_name': 'aenon/online_judge', 'size': '6070'}