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
  • DFS
  • BFS

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)


3
5
7
10
20
30

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)


10
5
3
7
20
30

In [ ]:

Binary Tree Traversal


In [17]:
def inOrderTraverse(node):
    if node:
        inOrderTraverse(node.left)
        print(node.data)
        inOrderTraverse(node.right)

In [18]:
inOrderTraverse(node1)


1
2
3
5

In [19]:
def preOrderTraverse(node):
    if node:
        print(node.data)
        preOrderTraverse(node.left)
        preOrderTraverse(node.right)

In [20]:
preOrderTraverse(node1)


3
2
1
5

In [21]:
def postOrderTraverse(node):
    if node:
        postOrderTraverse(node.left)
        postOrderTraverse(node.right)
        print(node.data)

In [22]:
postOrderTraverse(node1)


1
2
5
3

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 [ ]: