Solving Problems: Trees and Graphs

Common Packages and Methods

from IPython.display import SVG, HTML, IFrame
from IPython.display import display
from graphviz import Source
from collections import deque
from typing import List
from numpy import inf
import operator
import codecs
import os
import re

def visualize(text, height=220):
    text = "digraph BST_TEMP {" + text + "}"
    graph = Source(text)
    svgt = codecs.decode(graph.pipe(format='svg'),'UTF-8')
    regex_1 = r"height=\"[0-9]+pt\""
    regex_2 = r"width=\"[0-9]+pt\""
    subst = 'height="'+str(height)+'pt"'
    svgt = re.sub(regex_1, subst, svgt, 0, re.MULTILINE)
    svgt = re.sub(regex_2, subst, svgt, 0, re.MULTILINE)
    display(HTML("<br>"+svgt))
    
def arrow_string(a, b):
    return (str(a) + "->" + str(b) + ";")

Sum of Root To Leaf Binary Numbers

 

You are given the root of a binary tree where each node has a value 0 or 1. Each root-to-leaf path represents a binary number starting with the most significant bit. For example, if the path is 0 -> 1 -> 1 -> 0 -> 1, then this could represent 01101 in binary, which is 13.

For all leaves in the tree, consider the numbers represented by the path from the root to that leaf.

Return the sum of these numbers. The answer is guaranteed to fit in a 32-bits integer.

Example

code_temp = """
    <code>
        Input: root = [1,0,1,0,1,0,1]
        Output: 22
        Explanation: (100) + (101) + (110) + (111) = 4 + 5 + 6 + 7 = 22
    </code>
    <img style="width: 40%;" src="https://assets.leetcode.com/uploads/2019/04/04/sum-of-root-to-leaf-binary-numbers.png" />
"""
display(HTML(code_temp))

Input: root = [1,0,1,0,1,0,1] Output: 22 Explanation: (100) + (101) + (110) + (111) = 4 + 5 + 6 + 7 = 22

Solution

# Node Class
class Node:
    def __init__(self, data):
        self.data = data
        self.left = None
        self.right = None

# Example 1
root = Node(1)
root.left = Node(0)
root.left.left = Node(0)
root.left.right = Node(1)
root.right = Node(1)
root.right.left = Node(0)
root.right.right = Node(1)

class Solution_1:
    def return_nodes(self, root, bits_text):
        global sum_t
        bits_text += str(root.data)
        if root.left:
            self.return_nodes(root.left, bits_text)
        if root.right:
            self.return_nodes(root.right, bits_text)
        if root.left is None and root.right is None:
            sum_t += int(bits_text, 2)
    
    def sumRootToLeaf(self, root) -> int:
        global sum_t
        sum_t = 0
        self.return_nodes(root, "")
        return sum_t
    
sum_t = Solution_1().sumRootToLeaf(root)
print("Output:", sum_t)

Output: 22

Lowest Common Ancestor of a Binary Tree

 

Given a binary tree, find the lowest common ancestor (LCA) of two given nodes in the tree. According to the definition of LCA on Wikipedia: “The lowest common ancestor is defined between two nodes p and q as the lowest node in T that has both p and q as descendants (where we allow a node to be a descendant of itself).”

Example 1:

Input: root = [3,5,1,6,2,0,8,null,null,7,4], p = 5, q = 1
Output: 3
Explanation: The LCA of nodes 5 and 1 is 3.

Example 2:

Input: root = [3,5,1,6,2,0,8,null,null,7,4], p = 5, q = 4
Output: 5
Explanation: The LCA of nodes 5 and 4 is 5, since a node can be a descendant of itself according to the LCA definition.

Example 3:

Input: root = [1,2], p = 1, q = 2
Output: 1

Constraints:

• The number of nodes in the tree is in the range [2, 105].
• -109 <= Node.val <= 109
• All Node.val are unique.
• p != q
• p and q will exist in the tree.

# Definition for a binary tree node.
class TreeNode:
    def __init__(self, x):
        self.val = x
        self.left = None
        self.right = None

class Solution_1:
    # Using Pre-Order Traversal and storing paths (Cons: Memory Intensive)
    def lowestCommonAncestor(self, root: 'TreeNode', p: 'TreeNode', q: 'TreeNode') -> 'TreeNode':
        global path_to_p, path_to_q
        path_to_p, path_to_q = None, None
        
        def common(a, b):
            ans = None
            for i in a:
                if i in b: ans = i
            return ans
        
        def preorder(root, prev=[]):
            global path_to_p, path_to_q
            prev.append(root)
            if root == p: 
                path_to_p = prev.copy()
                if path_to_p and path_to_q: return
            elif root == q:
                path_to_q = prev.copy()
                if path_to_p and path_to_q: return
            if root.left: inorder(root.left, prev.copy())
            if root.right: inorder(root.right, prev.copy())
                
        preorder(root)
        return common(path_to_p, path_to_q)

class Solution_2:
    def __init__(self):
        self.ans = None
        
    def lowestCommonAncestor(self, root: 'TreeNode', p: 'TreeNode', q: 'TreeNode') -> 'TreeNode':
        # Recursive Backtracking Approach (Better than above)
        def recursive_tree(root):
            if not root: return False
            left = recursive_tree(root.left)
            right = recursive_tree(root.right)
            mid = (root == p) or (root == q)
            if (left + right + mid) >=2: self.ans = root
            return left or right or mid
        
        recursive_tree(root)
        return self.ans