Algorithms-Reference

Trees

Binary Tree Class

class TreeNode(object):
    def __init__(self, x):
        self.val = x
        self.left = None
        self.right = None

DFS in Tree

Iterative Solution

def dfs(self,root):
    stack=[]

    while root or stack:
        while root:
            stack.append(root)
            root=root.left

        node=stack.pop()
        print (node.val)
        root=node.right

Recursive Solution

# Inorder
def dfsInorder(self,node):
    if not node:
        return 
    
    self.dfsInorder(node.left)
    print (node.val)
    self.dfsInorder(node.right)

# Postorder
def dfsPostorder(self,node):
    if not node:
        return 
    
    self.dfsPostorder(node.left)
    self.dfsPostorder(node.right)
    print (node.val)

# Preorder
def dfsPreorder(self,node):
    if not node:
        return 
    
    print (node.val)    
    self.dfsPreorder(node.left)
    self.dfsPreorder(node.right)

BFS in Tree

def bfs(self,root):
    q = [root]
    q_u = []

    result=[]

    # Complexity remains same even if using two while loops. 
    # Using two while loops to print all elements at a particular depth 
    # Using one queue will attain the same result, just differentiating elements by depth will be difficult
    while q:
        while q:
            node = q.pop()
            if node:
                q_u.append(node.left)
                q_u.append(node.right)

                result.append(node.val)
        q=q_u[::-1]
        q_u=[]
        
    return result