Trees & Graphs — Advanced

# iterative max_height()
#def max_height(root):
#    if not root:
#        return 0
#    height = 0
#    queue = [root]
#    while queue:
#        height += 1
#        level = []
#        while queue:
#            node = queue.pop(0)
#            if node.left:
#                level.append(node.left)
#            if node.right:
#                level.append(node.right)
#        queue = level
#    return height

INT_MIN = -2**32
  
def canRepresentBST(pre): 
  
    # stack 
    s = [] 

    root = INT_MIN 
  
    for value in pre:  

        if value < root: 
            return False 

        # If value(pre[i]) is in right subtree of stack top,  
        # Keep removing items smaller than value 
        # and make the last removed item new root 
        while(len(s) > 0 and s[-1] < value) : 
            root = s.pop() 
          
        # Either stack is empty or value < root => push value 
        s.append(value) 
  
    return True
  
# Driver Program 
pre1 = [40 , 30 , 35 , 80 , 100] 
print('True' if canRepresentBST(pre1) else 'False')
pre2 = [40 , 30 , 35 , 20 ,  80 , 100] 
print('True' if canRepresentBST(pre2) else 'False')

'''
               1
           /      \
         2          3
      /     \         \
    4         5        6
  /                   /
 7                   8 
Input: Root of above Binary Tree
       k = 4

Output: The tree should be changed to following  
           1
        /     \
      2          3
     /             \
   4                 6
 /                  /
7                  8

There are 3 paths 
i) 1->2->4->7      path length = 4
ii) 1->2->5        path length = 3
iii) 1->3->6->8    path length = 4 

There is only one path " 1->2->5 " of length smaller than 4.  
The node 5 is the only node that lies only on this path, so 
node 5 is removed.
Nodes 2 and 1 are not removed as they are parts of other paths
of length 4 as well.

If k is 5 or greater than 5, then whole tree is deleted. 

If k is 3 or less than 3, then nothing is deleted
'''
pass

class Node:
        
    def __init__(self, data):
                
        self.data = data  
        self.left = self.right = None
          
# remove nodes on that are not on pathLen >= k 
def util_method(root, level, k) : 
  
    
    if (root == None):                                                               # base case  
        return None
  
    # postorder fashion traversal: if a leaf node path length < k,
    # then this node and all its ancestors until a node on another path are removed
    root.left = util_method(root.left, level + 1, k)
    root.right = util_method(root.right, level + 1, k)
  
    # if root = leaf node & its level < k, then remove it
    # check ancestor nodes until finding a node that's  part of another path
    if (root.left == None and
        root.right == None and level < k) :  
        return None
      
    # Return root  
    return root  
  

def remove_short_path_nodes(root, k) : 
    return util_method(root, 1, k)
  

def in_order(root) : 
  
    if (root):
                
        in_order(root.left)
        print(root.data, end = " " )
        in_order(root.right)

        
k = 4
root = Node(1)
root.left = Node(2)
root.right = Node(3)
root.left.left = Node(4)
root.left.right = Node(5)
root.left.left.left = Node(7)
root.right.right = Node(6)
root.right.right.left = Node(8)
print('Inorder traversal of initial tree' )  
in_order(root)
print()
print('Inorder traversal of modified tree')  
res = remove_short_path_nodes(root, k)
in_order(res)

### Remove nodes on root-to-leaf paths of length < k
If node X is on multiple root-to-leaf paths and if any of the paths >= k, then X is not deleted => node is deleted iff all paths going through it have lengths < k

Solution: do post order traversal. Before removing a node, check if all its children in the shorter path are removed. Two cases:  
i) This node becomes a leaf node in which case it needs to be deleted.  
ii) This node has another child on a path with length >= k. In that case it needs not to be deleted

Time c. O(n) where n = # nodes

'''
               1
           /      \
         2          3
      /     \         \
    4         5        6
  /                   /
 7                   8 
Input: Root of above Binary Tree
       k = 4

Output: The tree should be changed to following  
           1
        /     \
      2          3
     /             \
   4                 6
 /                  /
7                  8

There are 3 paths 
i) 1->2->4->7      path length = 4
ii) 1->2->5        path length = 3
iii) 1->3->6->8    path length = 4 

There is only one path " 1->2->5 " of length smaller than 4.  
The node 5 is the only node that lies only on this path, so 
node 5 is removed.
Nodes 2 and 1 are not removed as they are parts of other paths
of length 4 as well.

If k is 5 or greater than 5, then whole tree is deleted. 

If k is 3 or less than 3, then nothing is deleted
'''
pass

class Node:
        
    def __init__(self, data):
                
        self.data = data  
        self.left = self.right = None
          
# remove nodes on that are not on pathLen >= k 
def util_method(root, level, k) : 
  
    
    if (root == None):                                                               # base case  
        return None
  
    # postorder fashion traversal: if a leaf node path length < k,
    # then this node and all its ancestors until a node on another path are removed
    root.left = util_method(root.left, level + 1, k)
    root.right = util_method(root.right, level + 1, k)
  
    # if root = leaf node & its level < k, then remove it
    # check ancestor nodes until finding a node that's  part of another path
    if (root.left == None and
        root.right == None and level < k) :  
        return None
      
    # Return root  
    return root  
  

def remove_short_path_nodes(root, k) : 
    return util_method(root, 1, k)
  

def in_order(root) : 
  
    if (root):
                
        in_order(root.left)
        print(root.data, end = " " )
        in_order(root.right)

        
k = 4
root = Node(1)
root.left = Node(2)
root.right = Node(3)
root.left.left = Node(4)
root.left.right = Node(5)
root.left.left.left = Node(7)
root.right.right = Node(6)
root.right.right.left = Node(8)
print('Inorder traversal of initial tree' )  
in_order(root)
print()
print('Inorder traversal of modified tree')  
res = remove_short_path_nodes(root, k)
in_order(res)

# WORD LADDER - FOOL, POOL, POLL, POLE, PALE, SALE, SAGE
# Load wrods file and build graph
from collections import defaultdict
from itertools import product
import os


def build_graph(words):
    buckets = defaultdict(list)
    graph = defaultdict(set)

    for word in words:
        for i in range(len(word)):
            bucket = '{}_{}'.format(word[:i], word[i + 1:])
            buckets[bucket].append(word)

    # add vertices and edges for words in the same bucket
    for bucket, mutual_neighbors in buckets.items():
        for word1, word2 in product(mutual_neighbors, repeat=2):
            if word1 != word2:
                graph[word1].add(word2)
                graph[word2].add(word1)

    return graph


def get_words(vocabulary_file):
    for line in open(vocabulary_file, 'r'):
        yield line[:-1]  # remove newline character


vocabulary_file = 'vocabulary.txt' #os.path.join(os.path.dirname(__file__), 'vocabulary.txt')
word_graph = build_graph(get_words(vocabulary_file))

# BREADTH FIRST SEARCH IN GRAPH
from collections import deque


def traverse(graph, starting_vertex):
    visited = set()
    queue = deque([[starting_vertex]])
    while queue:
        path = queue.popleft()
        vertex = path[-1]
        yield vertex, path
        for neighbor in graph[vertex] - visited:
            visited.add(neighbor)
            queue.append(path + [neighbor])

if __name__ == '__main__':
    for vertex, path in traverse(word_graph, 'FOOL'):
        if vertex == 'SAGE':
            print(' -> '.join(path))

# DEPTH FIRST TRAVERSAL
# {'discovery': m, 'finish': n}, where the m and n are integers obtained by incrementing a counter before
# and after each time a new vertex is traversed

simple_graph = {
    'A': ['B', 'D'],
    'B': ['C', 'D'],
    'C': [],
    'D': ['E'],
    'E': ['B', 'F'],
    'F': ['C']
}


def depth_first_search(graph, starting_vertex):
    visited = set()
    counter = [0]
    traversal_times = defaultdict(dict)

    def traverse(vertex):
        visited.add(vertex)
        counter[0] += 1
        traversal_times[vertex]['discovery'] = counter[0]

        for next_vertex in graph[vertex]:
            if next_vertex not in visited:
                traverse(next_vertex)

        counter[0] += 1
        traversal_times[vertex]['finish'] = counter[0]

    # in this case start with just one vertex, but we could equally
    # dfs from all_vertices to produce a dfs forest
    traverse(starting_vertex)
    return traversal_times

traversal_times = depth_first_search(simple_graph, 'A')
traversal_times

# source = https://www.studytonight.com/python-programs/python-program-for-topological-sorting
from collections import defaultdict
class Graph:
    def __init__(self, directed=False):
        self.graph = defaultdict(list)
        self.directed = directed

    def Edge(self, frm, to):
        self.graph[frm].append(to)

        if self.directed is False:
            self.graph[to].append(frm)
        else:
            self.graph[to] = self.graph[to]

    def visit(self, s, visited, sortlist):
        visited[s] = True

        for i in self.graph[s]:
            if not visited[i]:
                self.visit(i, visited, sortlist)

        sortlist.insert(0, s)

    def topological_Sort(self):
        visited = {i: False for i in self.graph}

        sortlist = []
       
        for v in self.graph:
            if not visited[v]:
                self.visit(v, visited, sortlist)

        print(sortlist)

#driver code
if __name__ == '__main__':
 
    g = Graph(directed=True)

    g.Edge(1, 2)
    g.Edge(2, 3)
    g.Edge(3, 4)
    g.Edge(4, 5)
    g.Edge(5, 6)
    g.Edge(6, 7)
    g.Edge(7, 8)
    
    print("The Result after Topological Sort:")
    g.topological_Sort()

def iterative_dfs(graph, start):
        
    seen , q = set(), [start]                               # efficient set to look up nodes in
    path = []                                               # there was no good reason for this to be an argument in your code
    
    while q:
        v = q.pop()                                         # no reason not to pop from the end, where it's fast
        if v not in seen:
            path.append(v)
            seen.add(v)
            q.extend(graph[v])                              # this will add the nodes in a slightly different order
                                                            # if you want the same order, use reversed(graph[v])

    return path


def iterative_topological_sort(graph, start):
        
    seen = set()
    q = [start]
    
    stack = []                                               # path variable is gone, stack and order are new
    order = []                                               # order will be in reverse order at first
    
    while q:
        v = q.pop()
        if v not in seen:
            seen.add(v)                                      # no need to append to path any more
            q.extend(graph[v])

            while stack and v not in graph[stack[-1]]:       # new stuff here!
                order.append(stack.pop())
            stack.append(v)

    return stack + order[::-1]                               # new return value!

def recursive_dfs(graph, node):
    result = []
    seen = set()

    def recursive_helper(node):
        for neighbor in graph[node]:
            if neighbor not in seen:
                result.append(neighbor)                       # this line will be replaced below
                seen.add(neighbor)
                recursive_helper(neighbor)

    recursive_helper(node)
    return result


def recursive_topological_sort(graph, node):
    result = []
    seen = set()

    def recursive_helper(node):
        for neighbor in graph[node]:
            if neighbor not in seen:
                seen.add(neighbor)
                recursive_helper(neighbor)
        result.insert(0, node)                                 # this line replaces the result.append line

    recursive_helper(node)
    return result


graph = {
    'a': ['b', 'c'],
    'b': ['d'],
    'c': ['d'],
    'd': ['e'],
    'e': []
}
print(iterative_dfs(graph, 'a'))
print(iterative_topological_sort(graph, 'a'))
#print(recursive_dfs(graph, 'a'))                              # both recursive implementations provide results
#print(recursive_topological_sort(graph, 'a'))                 # different than iterative - why?

# OBJECT-BASED ADJACENCY LIST
# https://bradfieldcs.com/algos/graphs/representing-a-graph/ + Udemy
# neighbors = dict of vertices connected to this one and weights of edges to them; use set if no weights
class Vertex:
    def __init__(self, key):
        self.key = key
        self.neighbors = {}

    # add a connection from this vertex to another
    def add_neighbor(self, neighbor, weight=0):
        self.neighbors[neighbor] = weight

    def __str__(self):
        return '{} neighbors: {}'.format(
            self.key,
            [x.key for x in self.neighbors]
        )

    # get all of the vertices in the adjacency list
    def get_connections(self):
        return self.neighbors.keys()

    # get weight of the edge from this vertex to neighbor
    def get_weight(self, neighbor):
        return self.neighbors[neighbor]

# dict to map vertex names to vertex objects
class Graph(object):
    def __init__(self):
        self.verticies = {}

    # adding vertex to graph 
    def add_vertex(self, vertex):
        self.verticies[vertex.key] = vertex


    def get_vertex(self, key):
        try:
            return self.verticies[key]
        except KeyError:
            return None

    def __contains__(self, key):
        return key in self.verticies

    # connect vertices
    def add_edge(self, from_key, to_key, weight=0):
        if from_key not in self.verticies:
            self.add_vertex(Vertex(from_key))
        if to_key not in self.verticies:
            self.add_vertex(Vertex(to_key))
        self.verticies[from_key].add_neighbor(self.verticies[to_key], weight)
    
    # names of all vertices in graph
    def get_vertices(self):
        return self.verticies.keys()

    # iterate over all the vertex objects (or names by using get_vertices())
    def __iter__(self):
        return iter(self.verticies.values())

g = Graph()

for i in range(6):
    g.add_vertex(Vertex(i))
print(g.verticies)

g.add_edge(0, 1, 5)
g.add_edge(0, 5, 2)
g.add_edge(1, 2, 4)
g.add_edge(2, 3, 9)
g.add_edge(3, 4, 7)
g.add_edge(3, 5, 3)
g.add_edge(4, 0, 1)
g.add_edge(5, 4, 8)
g.add_edge(5, 2, 1)
for v in g:
    for w in v.get_connections():
        print('{} -> {}'.format(v.key, w.key))

"""
Given a binary tree, determine if it is a valid binary search tree (BST).

Assume a BST is defined as follows:

The left subtree of a node contains only nodes
with keys less than the node's key.
The right subtree of a node contains only nodes
with keys greater than the node's key.
Both the left and right subtrees must also be binary search trees.
Example 1:
    2
   / \
  1   3
Binary tree [2,1,3], return true.
Example 2:
    1
   / \
  2   3
Binary tree [1,2,3], return false.
"""


def is_bst(root):
    """
    :type root: TreeNode
    :rtype: bool
    """
    if not root:
        return True
    stack = []
    pre = None
    while root and stack:
        while root:
            stack.append(root)
            root = root.left
        root = stack.pop()
        if pre and root.val <= pre.val:
            return False
        pre = root
        root = root.right
    return True

#   Author: Tim Rijavec
#           tim@coder.si
#           http://coder.si

class avlnode(object):
    """
    A node in an avl tree.
    """

    def __init__(self, key):
                
        self.key = key
        self.left = None
        self.right = None
        
class avltree(object):    
    
    
    def __init__(self):
                
        self.node = None        
        self.height = -1
        # Balance factor 
        self.balance = 0
        
    def insert(self, key):
        """
        Insert new key into node
        """
        # Create new node
        n = avlnode(key)

        # Initial tree
        if not self.node:
            self.node = n
            self.node.left = avltree()
            self.node.right = avltree()
        # Insert key to the left subtree
        elif key < self.node.key:
            self.node.left.insert(key)
        # Insert key to the right subtree
        elif key > self.node.key:
            self.node.right.insert(key)
            
        # Rebalance tree if needed
        self.rebalance()
        
    def rebalance(self):
        """
        Rebalance tree. After inserting or deleting a node, 
        it is necessary to check each of the node's ancestors for consistency with the rules of AVL
        """

        # Check if we need to rebalance the tree
        #   update height
        #   balance tree
        self.update_heights(recursive=False)
        self.update_balances(False)

        # For each node checked, 
        #   if the balance factor remains −1, 0, or +1 then no rotations are necessary.
        while self.balance < -1 or self.balance > 1: 
            # Left subtree is larger than right subtree
            if self.balance > 1:

                # Left Right Case -> rotate y,z to the left
                if self.node.left.balance < 0:
                    #     x               x
                    #    / \             / \
                    #   y   D           z   D
                    #  / \        ->   / \
                    # A   z           y   C
                    #    / \         / \
                    #   B   C       A   B
                    self.node.left.rotate_left()
                    self.update_heights()
                    self.update_balances()

                # Left Left Case -> rotate z,x to the right
                #       x                 z
                #      / \              /   \
                #     z   D            y     x
                #    / \         ->   / \   / \
                #   y   C            A   B C   D 
                #  / \ 
                # A   B
                self.rotate_right()
                self.update_heights()
                self.update_balances()
            
            # Right subtree is larger than left subtree
            if self.balance < -1:
                
                # Right Left Case -> rotate x,z to the right
                if self.node.right.balance > 0:
                    #     y               y
                    #    / \             / \
                    #   A   x           A   z
                    #      / \    ->       / \
                    #     z   D           B   x
                    #    / \                 / \
                    #   B   C               C   D
                    self.node.right.rotate_right() # we're in case III
                    self.update_heights()
                    self.update_balances()

                # Right Right Case -> rotate y,x to the left
                #       y                 z
                #      / \              /   \
                #     A   z            y     x
                #        / \     ->   / \   / \
                #       B   x        A   B C   D 
                #          / \ 
                #         C   D
                self.rotate_left()
                self.update_heights()
                self.update_balances()

    def update_heights(self, recursive=True):
        """
        Update tree height

        Tree height is max height of either left or right subtrees +1 for root of the tree
        """
        if self.node: 
            if recursive: 
                if self.node.left: 
                    self.node.left.update_heights()
                if self.node.right:
                    self.node.right.update_heights()
            
            self.height = 1 + max(self.node.left.height, self.node.right.height)
        else: 
            self.height = -1

    def update_balances(self, recursive=True):
        """
        Calculate tree balance factor

        The balance factor is calculated as follows: 
            balance = height(left subtree) - height(right subtree). 
        """
        if self.node:
            if recursive:
                if self.node.left:
                    self.node.left.update_balances()
                if self.node.right:
                    self.node.right.update_balances()

            self.balance = self.node.left.height - self.node.right.height
        else:
            self.balance = 0 

            
    def rotate_right(self):
        """
        Right rotation
            set self as the right subtree of left subree
        """
        new_root = self.node.left.node
        new_left_sub = new_root.right.node
        old_root = self.node

        self.node = new_root
        old_root.left.node = new_left_sub
        new_root.right.node = old_root

    def rotate_left(self):
        """
        Left rotation
            set self as the left subtree of right subree
        """
        new_root = self.node.right.node
        new_left_sub = new_root.left.node
        old_root = self.node

        self.node = new_root
        old_root.right.node = new_left_sub
        new_root.left.node = old_root

    def delete(self, key):
        """
        Delete key from the tree

        Let node X be the node with the value we need to delete, 
        and let node Y be a node in the tree we need to find to take node X's place, 
        and let node Z be the actual node we take out of the tree.

        Steps to consider when deleting a node in an AVL tree are the following:

            * If node X is a leaf or has only one child, skip to step 5. (node Z will be node X)
                * Otherwise, determine node Y by finding the largest node in node X's left sub tree 
                    (in-order predecessor) or the smallest in its right sub tree (in-order successor).
                * Replace node X with node Y (remember, tree structure doesn't change here, only the values). 
                    In this step, node X is essentially deleted when its internal values were overwritten with node Y's.
                * Choose node Z to be the old node Y.
            * Attach node Z's subtree to its parent (if it has a subtree). If node Z's parent is null, 
                update root. (node Z is currently root)
            * Delete node Z.
            * Retrace the path back up the tree (starting with node Z's parent) to the root, 
                adjusting the balance factors as needed.
        """
        if self.node != None:
            if self.node.key == key:
                # Key found in leaf node, just erase it
                if not self.node.left.node and not self.node.right.node:
                    self.node = None
                # Node has only one subtree (right), replace root with that one
                elif not self.node.left.node:                
                    self.node = self.node.right.node
                # Node has only one subtree (left), replace root with that one
                elif not self.node.right.node:
                    self.node = self.node.left.node
                else:
                    # Find  successor as smallest node in right subtree or
                    #       predecessor as largest node in left subtree
                    successor = self.node.right.node  
                    while successor and successor.left.node:
                        successor = successor.left.node

                    if successor:
                        self.node.key = successor.key

                        # Delete successor from the replaced node right subree
                        self.node.right.delete(successor.key)

            elif key < self.node.key:
                self.node.left.delete(key)

            elif key > self.node.key:
                self.node.right.delete(key)

            # Rebalance tree
            self.rebalance()

    def inorder_traverse(self):
        """
        Inorder traversal of the tree
            Left subree + root + Right subtree
        """
        result = []

        if not self.node:
            return result
        
        result.extend(self.node.left.inorder_traverse())
        result.append(self.node.key)
        result.extend(self.node.right.inorder_traverse())

        return result

    def display(self, node=None, level=0):
        if not node:
            node = self.node

        if node.right.node:
            self.display(node.right.node, level + 1)
            print ('\t' * level), ('    /')

        print ('\t' * level), node

        if node.left.node:
            print ('\t' * level), ('    \\')
            self.display(node.left.node, level + 1)

# Demo    
if __name__ == "__main__": 
    tree = avltree()
    data = [1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11]

    from random import randrange
    for key in data:  
        tree.insert(key)

    for key in [4,3]:
        tree.delete(key)
        
    print(tree.inorder_traverse())
    tree.display()

"""
Methods:
    1. Insert
    2. Search
    3. Size
    4. Traversal (Preorder, Inorder, Postorder)
"""

import unittest

class Node(object):
    def __init__(self, data):
        self.data = data
        self.left = None
        self.right = None

class BST(object):
    def __init__(self):
        self.root = None

    def get_root(self):
        return self.root

    """
        Get the number of elements
        Using recursion. Complexity O(logN)
    """
    def size(self):
        return self.recur_size(self.root)

    def recur_size(self, root):
        if root is None:
            return 0
        else:
            return 1 + self.recur_size(root.left) + self.recur_size(root.right)

    """
        Search data in bst
        Using recursion. Complexity O(logN)
    """
    def search(self, data):
        return self.recur_search(self.root, data)

    def recur_search(self, root, data):
        if root is None:
            return False
        if root.data == data:
            return True
        elif data > root.data:     # Go to right root
            return self.recur_search(root.right, data)
        else:                      # Go to left root
            return self.recur_search(root.left, data)

    """
        Insert data in bst
        Using recursion. Complexity O(logN)
    """
    def insert(self, data):
        if self.root:
            return self.recur_insert(self.root, data)
        else:
            self.root = Node(data)
            return True

    def recur_insert(self, root, data):
        if root.data == data:      # The data is already there
            return False
        elif data < root.data:     # Go to left root
            if root.left:          # If left root is a node
                return self.recur_insert(root.left, data)
            else:                  # left root is a None
                root.left = Node(data)
                return True
        else:                      # Go to right root
            if root.right:         # If right root is a node
                return self.recur_insert(root.right, data)
            else:
                root.right = Node(data)
                return True

    """
        Preorder, Postorder, Inorder traversal bst
    """
    def preorder(self, root):
        if root:
            print(str(root.data), end = ' ')
            self.preorder(root.left)
            self.preorder(root.right)

    def inorder(self, root):
        if root:
            self.inorder(root.left)
            print(str(root.data), end = ' ')
            self.inorder(root.right)

    def postorder(self, root):
        if root:
            self.postorder(root.left)
            self.postorder(root.right)
            print(str(root.data), end = ' ')

"""
    The tree is created for testing:

                    10
                 /      \
               6         15
              / \       /   \
            4     9   12      24
                 /          /    \
                7         20      30
                         /
                       18
"""

class TestSuite(unittest.TestCase):
    def setUp(self):
        self.tree = BST()
        self.tree.insert(10)
        self.tree.insert(15)
        self.tree.insert(6)
        self.tree.insert(4)
        self.tree.insert(9)
        self.tree.insert(12)
        self.tree.insert(24)
        self.tree.insert(7)
        self.tree.insert(20)
        self.tree.insert(30)
        self.tree.insert(18)

    def test_search(self):
        self.assertTrue(self.tree.search(24))
        self.assertFalse(self.tree.search(50))

    def test_size(self):
        self.assertEqual(11, self.tree.size())

#if __name__ == '__main__':
unittest.main()

class BSTIterator:
    def __init__(self, root):
        self.stack = []
        while root:
            self.stack.append(root)
            root = root.left

    def has_next(self):
        return bool(self.stack)

    def next(self):
        node = self.stack.pop()
        tmp = node
        if tmp.right:
            tmp = tmp.right
            while tmp:
                self.stack.append(tmp)
                tmp = tmp.left
        return node.val