Lecture_Notes/imperfect_notes/pragy/Binary Trees 2.md

Binary Trees 2

Lowest Common Ancestor

LCA(n1, n2) is the node which is accessible from both n1, n2 (while going up), and is farthest from the root Given a Tree and 2 nodes, find LCA k-ary tree

Approach 1:

• traverse from each node to root - bottom up
• compare the two paths from left to right
• O(n^2) time, O(n) space

Approach 2:

• traverse from each node to root - bottom up
• compare from root to node - top down
• O(n) time, O(n) space

Approach 3:

• don't store all parents. Use linked list intersection technique
• count the height of each path.
• traverse the longer path so height is same
• move up together
• stop when same node
• O(1) space

Can't go from child to parent? Don't have pointers to nodee we have values which must be searched Distinct values

def lca(key1, key2, node):
    if node.value in [key1, key2]:
        return node
    left = lca(key1, key2, node.left)
    right = lca(key1, key2, node.right)
    if left is not None and right is not None:
        return node
    if left is not None:
        return left
    if right is not None:
        return right
    return None
    
lca(key1, key2, root)

---

Isomorphism

Rotate tree to reach another row

def isomorphic(node1, node2):
    if node1 != node2:
        return False
        
    # binary
    if isomorphic(node1.left, node2.left) and isomorphic(node1.right, node2.right):
        return True
    if isomorphic(node1.left, node2.right) and isomorphic(node1.right, node2.left):
        return True
    return False
    # O(n). Each node visited at most twice
    
    # k-ary
    for children1 in permute(node1.children):
        for children2 in permute(node2.children):
            passed = True
            for c1, c2 in zip(children1, children2):
                if not isomorphic(c1, c2):
                    passed = False
                    break
            if passed:
                return True
    return False
    
    # sort tree in level order recursively first, then compare

---

Longest Increasing Consequtive Sequence

has to be top-down has to be connected has to be continuous (1-2-3 is okay, 1-3-5 is not)

• recursive
• func returns length of the LICS at node
• find LICS of left and right
• if left = node + 1, then LICS+1
• max of left, right

---

Create Next Pointers with O(1) space

• Simple using O(n) space. Just do level order traversal
• can't use recursion either, because have to maintain call stack, which is O(h)
• todo

level_start = root

while level_start:
    cur = level_start
    while cur is not None:
        if cur.left:
            if cur.right:
                cur.left.next = cur.right
            else:
                cur.left.next = get_next_child(cur)
        if cur.right:
            cur.right.next = get_next_child(cur)
            
        cur = cur.next
    if level_start.left:
        level_start = level_start.left
    elif level_start.right:
        level_start = level_start.right
    else:
        level_start = None

def get_next_child(node):
    iterate to get the child, till children exist
    if not, then move to node.next
    guaranteed to have precomputed the next

---

Boundary of tree

Tree of same sum

---

Why cant decide tree using pre+post order? why need inorder?

inorder: lst root rst preorder: root lst rst postorder: lst rst root

if just have preorder+postorder, can't separate lst-rst