Lecture_Notes/imperfect_notes/pragy/Trees & Graphs.md

Trees and Graphs

Graph:

• nodes
• edges: pairs of nodes that are connected
• directed/undirected
• weighted/unweighted

Trees:

• graphs with constraints
• connected
• acyclic
• rooted - contrast with graph
• node has 0 or more children
• node with 0 children is leaf
• node with 1 or more children is non-leaf
• each node has a parent - except for the root
• so, n-1 edges
• since we can make levels, it is a hierarchical DS

K-ary Tree:

• node can have at most k children

---

Binary Trees

    o
   / \
  o   o
   \  |\
    o o o

• Each node has exactly 1 parent (except root)
• Each node has at most 2 children

Node:
    value
    Node left_child
    Node right_child
    # typically, we also keep track of parent
    Node parent

• Full BT - 2^{l+1} - 1 nodes, if l levels
• Complete BT - full on penultimate level. Nodes in last level fill from the left
• BST
• Balanced Tree
• ...

---

Traversals

• DFS:

        o
     /     \
  [LST]   [RST]
  Left and Right subtrees
  

  • preorder: whatever operation, do on the node first, then LST, then RST
  • inorder: LST, Node, RST
  • postorder: LST, RST, Node
  • Recursive:

    def preorder(node):
        if node is null:
            return
        func(node)  # print
        preorder(node.left)
        preorder(node.right)
    

  • Iterative:
    • show how the recursion works using a call stack
    • so, use a stack - just remember the order to push nodes in

• level-order / bfs

---

Zig Zag traversal

   4
 6   8
1 3 2 5
========
4 | 8 6 | 1 3 2 5

def zigzag(A):
    queue = [A]
    result = []
    level = 0
    while queue:
        n = len(queue)
        vals = [x.val for x in queue]
        if level % 2 == 1:
            vals = vals[::-1]
        result.append(vals)
        for i in range(n):
            item = queue.pop()
            if item.left:
                queue.append(item.left)
            if item.right:
                queue.append(item.right)
        level += 1
    return result

---

Vertical traversal

  4
 6 8
1 3 5
=====
1 | 6 | 4 3 | 8 | 5 

If two children, put them in any order

store dict of lists of distance from mid move left = distance - 1 move left = distance + 1

---

Tree from Inorder + Preorder

Given Preporder and Inorder traversals of a Binary Tree, create the tree

• first element of preorder is the Root
• Find root in In-order traversal. Everything on left is in the LST and everything to the right is in the RST
• Recurse

def build(inorder, preorder, in_start, in_end):
    if in_start > in_end:
        return None
    node = Node(preorder[pre_index])
    pre_index += 1
    if in_start == in_end :
        return node

    inIndex = search(inorder, in_start, in_end, node.data)
    node.left = build(inorder, preorder, in_start, inIndex-1)
    node.right = build(inorder, preorder, inIndex + 1, in_end)
    return node

def search(arr, start, end, value):
    for i in range(start, end + 1):
        if arr[i] == value:
            return i

inorder = ['D', 'B', 'E', 'A', 'F', 'C']
preorder = ['A', 'B', 'D', 'E', 'C', 'F']
pre_index = 0
root = build(inorder, preorder, 0, len(inorder) - 1)

• search can be made O(1) or O(\log n) by storing in hashmap

---

Check Valid Traversals

Given Preorder, Inorder and Postorder, check if they represent the same tree

• Use any pair with inorder to create the tree. Then check the remaining order by traversing the tree

---

Check Balanced

Given Tree, check if balanced

\Bigl | h(\text{left}) - h(\text{right}) \Bigr | \leq c

Holds true for all nodes

def check(node):
    if node is null:
        return 0
    left_height, left_balanced = check(node.left)
    right_height, right_balanced = check(node.right)
    height = 1 + max(left_height, right_height)
    balanced = abs(left_height - right_height) < 1
                and left_balanced
                and right_balanced
    return height, balanced