Lecture_Notes/imperfect_notes/pragy/Binary Trees 2.md
2020-03-19 12:51:33 +05:30

3.6 KiB

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