# ---
# jupyter:
#   jupytext:
#     text_representation:
#       extension: .py
#       format_name: light
#       format_version: '1.5'
#       jupytext_version: 1.14.4
#   kernelspec:
#     display_name: Python 2
#     language: python
#     name: python2
# ---

# +
class node:
    """An implementation of a node, which tracks a value,
    left and right children, anda parent.
    """
    def __init__(self, v=None, l=None, r=None, p=None):
        self.v = v
        self.l = l
        self.r = r
        self.p = p
        
class q:
    """An implementation of a queue
    """
    def __init__(self, v):
        if v is not None:
            self.first = self.last = node(v)
        else:
            self.first=None
            self.last=None
    
    def enq(self, v):
        """Add an element to the end of a queue
        """
        ## If the queue is empty, add a single node
        if self.last is None:
            self.first = self.last = node(v)
        else:
            ### if the queue is not empty, add a not at the end of the queue
            old_last = self.last
            self.last = node(v)
            old_last.l = self.last
    
    def deq(self):
        """Remove the first element of a queue
        """
        if self.first is None:
            return None
        elif self.first is self.last: ## in this case there is only one node
            out = self.first
            self.first = None
            self.last = None
            return out.v
        else: ## In this case there is more than one node
            out = self.first
            self.first = out.l
            return out.v


# +
class tree:
    """Binary search tree that allows for insertion, deletion, and traversals.
    """
    def __init__(self, v=None):
        self.root = node(v=v)
        
    def insert(self, v, current=None):
        """Insert an element, always as a leaf.
        """
        if current is None:
            current = self.root
        if current is None:
            current = node(v=v)
        if current.v is None:
            current.v = v
        elif current.v <= v:
            if current.r is None:
                current.r = node(v, p=current)
                current.r.p = current
            else:
                self.insert(v, current.r)
        else:
            if current.l is None:
                current.l = node(v, p=current)
                current.l.p = current
            else:
                self.insert(v, current.l)
                
    def delete(self, v, current=None):
        """Find an node with a value and delete it.
        """
        if current is None:
            current = self.root
        if current.v is None:
            raise ValueError("Value %s not found" %v)
        if current.v == v:
            if current.l is None and current.r is None:
                current = None
            elif current.l is not None:
                p = current.p
                p.l = current.l
                current.l.p = p
            else:
                p = current.p
                p.r = current.r
                current.r.p = p
        if current.v > v and current.l is not None:
            self.delete(v, current=current.l)
        if current.v < v and current.r is not None:
            self.delete(v, current=current.r)
            
#################### Traversals ####################
            
    def pre_order(self, current=None):
        """Recursively traverse elements, in the order
        root --> left --> right
        
        The same order as DFS.
        """
        if current is None:
            current = self.root
        yield current.v
        if current.l is not None:
            for el in self.pre_order(current=current.l):
                yield el
        if current.r is not None:
            for el in self.pre_order(current=current.r):
                yield el
    
    def in_order(self, current=None):
        """Recursively traverse elements, in the order
        left --> root --> right
        
        Should return the elements in order for a binary search tree.
        """
        if current is None:
            current = self.root
        if current.l is not None:
            for el in self.in_order(current=current.l):
                yield str(el)
        yield current.v
        if current.r is not None:
            for el in self.in_order(current=current.r):
                yield str(el)
                
    def post_order(self, current=None):
        """Recursively traverse elements, in the order
        left --> right --> root
        """
        if current is None:
            current = self.root
        if current.l is not None:
            for el in self.post_order(current=current.l):
                yield el
        if current.r is not None:
            for el in self.post_order(current=current.r):
                yield el
        yield current.v
        
    def BFS(self, current=None):
        """Traverse the nodes in breath-first order.
        
        Uses a queue to store future nodes to traverse.
        
        Elements will display ordered first by generation, 
        and then from left to right
        """
        if current is None:
            current = self.root
        Q = q(current)
        while Q.first is not None:
            current = Q.deq()
            for child in [current.l, current.r]:
                if child is not None:
                    Q.enq(child)
            yield current.v
            
    def DFS(self, current=None):
        """Traverse the nodes in depth-first order.
        
        Uses a stack to store future nodes to traverse.
        
        Elements will displayed in order for a binary search tree.
        
        Should give the same result as pre-order traversal.
        """
        if current is None:
            current = self.root
        S = [current]
        while S:
            current = S.pop()
            yield current.v
            for child in [current.r, current.l]:
                if child is not None:
                    S.append(child)


# -

#################### Example ####################
T = tree()
for el in [4,5,7,6,3,2,1]:
    T.insert(el)

for el in T.pre_order():
    print el

for el in T.in_order():
    print el

for el in T.post_order():
    print el

for el in T.BFS():
    print el

for el in T.DFS():
    print el











StarcoderdataJupyterScriptsDedupFiltered