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

Reference

https://github.com/buy/cc150 https://github.com/kdn251/interviews/tree/master/CrackingTheCodingInterview



In [1]:

    
# 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'])

Implementation of a Tree Node



In [2]:

    
from collections import defaultdict



In [3]:

    
class Node:
    def __init__(self,data):
        self.data = data
        self.children = defaultdict(Node)



In [ ]:

Implementation of a Binary Tree



In [12]:

    
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)



In [16]:

    
node1 = Node(3)

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

node1.left.add_left(1)

Binary Tree with defaultdict



In [109]:

    
def inOrderTraverse(n):
    if BT[n]:
        if BT[n]['left']:
            inOrderTraverse(BT[n]['left'])
        print(n)
        if BT[n]['right']:
            inOrderTraverse(BT[n]['right'])



In [110]:

    
BT = defaultdict(lambda: {'left': None, 'right': None})



In [111]:

    
BT[10]['left'] = 5
BT[5]['left'] = 3
BT[5]['right'] = 7
BT[10]['right'] = 20
BT[20]['right'] = 30



In [112]:

    
inOrderTraverse(10)



In [113]:

    
def preOrderTraverse(n):
    if BT[n]:
        print(n)
        if BT[n]['left']:
            preOrderTraverse(BT[n]['left'])
        if BT[n]['right']:
            preOrderTraverse(BT[n]['right'])



In [114]:

    
preOrderTraverse(10)



In [ ]:

Binary Tree Traversal



In [17]:

    
def inOrderTraverse(node):
    if node:
        inOrderTraverse(node.left)
        print(node.data)
        inOrderTraverse(node.right)



In [18]:

    
inOrderTraverse(node1)



In [19]:

    
def preOrderTraverse(node):
    if node:
        print(node.data)
        preOrderTraverse(node.left)
        preOrderTraverse(node.right)



In [20]:

    
preOrderTraverse(node1)



In [21]:

    
def postOrderTraverse(node):
    if node:
        postOrderTraverse(node.left)
        postOrderTraverse(node.right)
        print(node.data)



In [22]:

    
postOrderTraverse(node1)

Implementation of an Adjacency List



In [23]:

    
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)

Implementation of an Adjacency Matrix



In [40]:

    
adjacencyMatrix = defaultdict(lambda: defaultdict(bool))



In [41]:

    
for (k, v) in [
    (1, 3),
    (2, 3),
    (1, 6),
    (6, 2)
]:
    adjacencyMatrix[k][v] = True
    adjacencyMatrix[v][k] = True



In [42]:

    
adjacencyMatrix[2]









    Out[42]:





defaultdict(bool, {3: True, 6: True})



In [ ]:



In [43]:

    
adjacencyMatrix[0][1]









    Out[43]:





False

4.1 Route Between Nodes



In [55]:

    
from collections import deque



In [64]:

    
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



In [77]:

    
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

5 <-- 0 --> 1 <-- 2
         ↘  ↓  ↘  ↑
            4 <-- 3



In [82]:

    
for (a, b) in [
    (2, 5),
    (0, 5),
    (5, 0),
    (4, 5),
    (0, 3),
    (3, 0)
]:
    print("({}, {}) => {}".format(a, b, hasRoute(adjacencyMatrix, a, b)))









    



(2, 5) => False
(0, 5) => True
(5, 0) => False
(4, 5) => False
(0, 3) => True
(3, 0) => False

4.2 Minimal Tree



In [119]:

    
mylist = [n for n in range(4, 17)]



In [120]:

    
mylist









    Out[120]:





[4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 14, 15, 16]



In [121]:

    
def minBST(mylist):
    def createMinBST(mylist, start, end):
        if end < start:
            return None
        mid = (start + end) // 2









    



  File "<ipython-input-121-8a804d3281cf>", line 2
    def createMinBST(mylist, start, end):
                                         ^
SyntaxError: unexpected EOF while parsing



In [123]:

    
3//2









    Out[123]:





1

4.3 List of Depths

4.4 Check Balanced

Define a binary tree



In [49]:

    
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)



In [46]:

    
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)



In [54]:

    
root = Node('root')
root.left = Node("left")
root.right = Node("right")
root.left.left = Node("left 2")
root.left.right = Node("left-right")



In [55]:

    
getHeight(root)









    Out[55]:





3



In [56]:

    
isBalanced(root)









    Out[56]:





True

Kr Tree



In [1]:

    
inputList = [[1,4], [1,5], [2,5], [3,6], [6,7]]



In [5]:

    
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)



In [6]:

    
myTree = Tree()



In [25]:

    
def Node(data=None):
    return {
        "data": data,
        "children": defaultdict(Node)
    }



In [26]:

    
myNode = Node(3)



In [29]:

    
myNode['children'][1] = 5



In [ ]:



In [ ]:



In [17]:

    
myTree = Tree()



In [18]:









    Out[18]:





defaultdict(<function __main__.Tree>, {})



In [ ]:



In [8]:

    
inputDict









    Out[8]:





{1: 5, 2: 5, 3: 6, 6: 7}



In [ ]: