Binary Tree Bottom-Up DFS¶

Table of Contents¶

104. Maximum Depth of Binary Tree¶

LeetCode | LeetCode CH (Easy)
Tags: tree, depth first search, breadth first search, binary tree

104. Maximum Depth of Binary Tree - Python Solution

from collections import deque
from typing import Optional

from binarytree import Node as TreeNode
from binarytree import build


# Recursive
def maxDepthRecursive(root: Optional[TreeNode]) -> int:
    if not root:
        return 0

    left = maxDepthRecursive(root.left)
    right = maxDepthRecursive(root.right)

    return 1 + max(left, right)


# DFS
def maxDepthDFS(root: Optional[TreeNode]) -> int:
    res = 0

    def dfs(node, cnt):
        if node is None:
            return
        cnt += 1
        nonlocal res
        res = max(res, cnt)

        dfs(node.left, cnt)
        dfs(node.right, cnt)

    dfs(root, 0)

    return res


# Iterative
def maxDepthIterative(root: Optional[TreeNode]) -> int:
    if not root:
        return 0

    q = deque([root])
    res = 0

    while q:
        res += 1
        n = len(q)

        for _ in range(n):
            node = q.popleft()
            if node.left:
                q.append(node.left)
            if node.right:
                q.append(node.right)

    return res


root = [1, 2, 2, 3, 4, None, None, None, None, 5]
root = build(root)
print(root)
#     ____1
#    /     \
#   2__     2
#  /   \
# 3     4
#      /
#     5
print(maxDepthRecursive(root))  # 4
print(maxDepthIterative(root))  # 4
print(maxDepthDFS(root))  # 4

111. Minimum Depth of Binary Tree¶

LeetCode | LeetCode CH (Easy)
Tags: tree, depth first search, breadth first search, binary tree

111. Minimum Depth of Binary Tree - Python Solution

from collections import deque
from typing import Optional

from binarytree import Node as TreeNode
from binarytree import build


# Iterative
def minDepthIterative(root: Optional[TreeNode]) -> int:
    if not root:
        return 0

    q = deque([root])
    res = 0

    while q:
        res += 1

        for _ in range(len(q)):
            node = q.popleft()

            if not node.left and not node.right:
                return res

            if node.left:
                q.append(node.left)
            if node.right:
                q.append(node.right)


# Recursive
def minDepthRecursive(root: Optional[TreeNode]) -> int:
    if root is None:
        return 0

    if root.left is None and root.right is not None:
        return 1 + minDepthRecursive(root.right)
    if root.left is not None and root.right is None:
        return 1 + minDepthRecursive(root.left)

    return 1 + min(minDepthRecursive(root.left), minDepthRecursive(root.right))


root = [1, 2, 2, 3, 4, None, None, None, None, 5]
root = build(root)
print(root)
"""
    ____1
   /     \
  2__     2
 /   \
3     4
     /
    5

"""
print(minDepthIterative(root))  # 2
print(minDepthRecursive(root))  # 2

965. Univalued Binary Tree¶

LeetCode | LeetCode CH (Easy)
Tags: tree, depth first search, breadth first search, binary tree

100. Same Tree¶

LeetCode | LeetCode CH (Easy)
Tags: tree, depth first search, breadth first search, binary tree

100. Same Tree - Python Solution

from collections import deque
from typing import Optional

from binarytree import build


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


# 1. Recursive
def isSameTreeRecursive(p: Optional[TreeNode], q: Optional[TreeNode]) -> bool:
    if not p and not q:
        return True
    if not p or not q:
        return False
    if p.val != q.val:
        return False

    return isSameTreeRecursive(p.left, q.left) and isSameTreeRecursive(
        p.right, q.right
    )


# 2. Iterative with queue
def isSameTreeIterativeQueue(
    p: Optional[TreeNode], q: Optional[TreeNode]
) -> bool:
    queue = deque([(p, q)])

    while queue:
        p, q = queue.popleft()

        if not p and not q:
            continue
        if not p or not q:
            return False
        if p.val != q.val:
            return False

        queue.append((p.left, q.left))
        queue.append((p.right, q.right))

    return True


# 3. Iterative with stack
def isSameTreeIterativeStack(
    p: Optional[TreeNode], q: Optional[TreeNode]
) -> bool:
    stack = [(p, q)]

    while stack:
        n1, n2 = stack.pop()

        if not n1 and not n2:
            continue
        if not n1 or not n2:
            return False
        if n1.val != n2.val:
            return False

        stack.append((n1.left, n2.left))
        stack.append((n1.right, n2.right))

    return True


p1 = build([1, 2, 3])
q1 = build([1, 2, 3])
p2 = build([1, 2])
q2 = build([1, None, 2])

print(isSameTreeRecursive(p1, q1))  # True
print(isSameTreeRecursive(p2, q2))  # False
print(isSameTreeIterativeQueue(p1, q1))  # True
print(isSameTreeIterativeQueue(p2, q2))  # False
print(isSameTreeIterativeStack(p1, q1))  # True
print(isSameTreeIterativeStack(p2, q2))  # False

101. Symmetric Tree¶

LeetCode | LeetCode CH (Easy)
Tags: tree, depth first search, breadth first search, binary tree

101. Symmetric Tree - Python Solution

from collections import deque
from typing import Optional

from binarytree import Node as TreeNode
from binarytree import build


# Recursive
def isSymmetricRecursive(root: Optional[TreeNode]) -> bool:
    if not root:
        return True

    def check(left, right):
        if left is right:
            return True
        if not left or not right or left.val != right.val:
            return False
        outside = check(left.left, right.right)
        inside = check(left.right, right.left)
        return outside and inside

    return check(root.left, root.right)


# Iterative
def isSymmetricIterative(root: Optional[TreeNode]) -> bool:
    if not root:
        return True

    q = deque()
    q.append(root.left)
    q.append(root.right)

    while q:
        left = q.popleft()
        right = q.popleft()

        if not left and not right:
            continue

        if not left or not right or left.val != right.val:
            return False

        q.append(left.left)
        q.append(right.right)
        q.append(left.right)
        q.append(right.left)

    return True


root = [1, 2, 2, 3, 4, 4, 3]
root = build(root)
print(root)
#     __1__
#    /     \
#   2       2
#  / \     / \
# 3   4   4   3
print(isSymmetricRecursive(root))  # True
print(isSymmetricIterative(root))  # True

951. Flip Equivalent Binary Trees¶

LeetCode | LeetCode CH (Medium)
Tags: tree, depth first search, binary tree

1379. Find a Corresponding Node of a Binary Tree in a Clone of That Tree¶

LeetCode | LeetCode CH (Easy)
Tags: tree, depth first search, breadth first search, binary tree

110. Balanced Binary Tree¶

LeetCode | LeetCode CH (Easy)
Tags: tree, depth first search, binary tree

110. Balanced Binary Tree - Python Solution

from typing import Optional

from binarytree import build


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


# Recursive
def isBalanced(root: Optional[TreeNode]) -> bool:
    def getHeight(node):
        if not node:
            return 0

        # post order
        leftHeight = getHeight(node.left)
        rightHeight = getHeight(node.right)

        if leftHeight == -1 or rightHeight == -1:
            return -1

        if abs(leftHeight - rightHeight) > 1:
            return -1
        else:
            return 1 + max(leftHeight, rightHeight)

    if getHeight(root) != -1:
        return True
    else:
        return False


root = [3, 9, 20, None, None, 15, 7]
root = build(root)
print(root)
#   3___
#  /    \
# 9     _20
#      /   \
#     15    7
print(isBalanced(root))  # True

226. Invert Binary Tree¶

LeetCode | LeetCode CH (Easy)
Tags: tree, depth first search, breadth first search, binary tree

226. Invert Binary Tree - Python Solution

from typing import Optional

from binarytree import build


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


# Recursive
def invertTreeRecursive(root: Optional[TreeNode]) -> Optional[TreeNode]:
    if not root:
        return root

    root.left, root.right = root.right, root.left

    invertTreeRecursive(root.left)
    invertTreeRecursive(root.right)

    return root


# Iterative
def invertTreeIterative(root: Optional[TreeNode]) -> Optional[TreeNode]:
    if not root:
        return root

    stack = [root]

    while stack:
        node = stack.pop()

        node.left, node.right = node.right, node.left
        if node.left:
            stack.append(node.left)
        if node.right:
            stack.append(node.right)

    return root


root = build([4, 2, 7, 1, 3, 6, 9])
print(root)
#     __4__
#    /     \
#   2       7
#  / \     / \
# 1   3   6   9
invertedRecursive = invertTreeRecursive(root)
print(invertedRecursive)
#     __4__
#    /     \
#   7       2
#  / \     / \
# 9   6   3   1
root = build([4, 2, 7, 1, 3, 6, 9])
invertedIterative = invertTreeIterative(root)
print(invertedIterative)
#     __4__
#    /     \
#   7       2
#  / \     / \
# 9   6   3   1

617. Merge Two Binary Trees¶

LeetCode | LeetCode CH (Easy)
Tags: tree, depth first search, breadth first search, binary tree

617. Merge Two Binary Trees - Python Solution

from typing import List, Optional


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


def mergeTrees(
    root1: Optional[TreeNode], root2: Optional[TreeNode]
) -> Optional[TreeNode]:

    if not root1:
        return root2
    if not root2:
        return root1

    root = TreeNode()

    root.val += root1.val + root2.val
    root.left = mergeTrees(root1.left, root2.left)
    root.right = mergeTrees(root1.right, root2.right)

    return root


root1 = TreeNode(1)
root1.left = TreeNode(3)
root1.right = TreeNode(2)
root1.left.left = TreeNode(5)
#     1
#    / \
#   3   2
#  /
# 5

root2 = TreeNode(2)
root2.left = TreeNode(1)
root2.right = TreeNode(3)
root2.left.right = TreeNode(4)
root2.right.right = TreeNode(7)
#     2
#    / \
#   1   3
#    \   \
#     4   7

root = mergeTrees(root1, root2)
#     3
#    / \
#   4   5
#  / \   \
# 5   4   7

2331. Evaluate Boolean Binary Tree¶

LeetCode | LeetCode CH (Easy)
Tags: tree, depth first search, binary tree

2331. Evaluate Boolean Binary Tree - Python Solution

from typing import Optional

from binarytree import build


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


# Recursive
def evaluateTree(root: Optional[TreeNode]) -> bool:
    if not root.left and not root.right:
        return root.val

    left = evaluateTree(root.left)
    right = evaluateTree(root.right)

    if root.val == 2:
        return left or right
    elif root.val == 3:
        return left and right


root = build([2, 1, 3, None, None, 0, 1])
print(root)
#   2__
#  /   \
# 1     3
#      / \
#     0   1
boolTree = build(["OR", "True", "AND", None, None, "False", "True"])
print(boolTree)
#    __OR_______
#   /           \
# True        __AND_
#            /      \
#         False     True
print(evaluateTree(root))  # 1

508. Most Frequent Subtree Sum¶

LeetCode | LeetCode CH (Medium)
Tags: hash table, tree, depth first search, binary tree

563. Binary Tree Tilt¶

LeetCode | LeetCode CH (Easy)
Tags: tree, depth first search, binary tree

606. Construct String from Binary Tree¶

LeetCode | LeetCode CH (Medium)
Tags: string, tree, depth first search, binary tree

2265. Count Nodes Equal to Average of Subtree¶

LeetCode | LeetCode CH (Medium)
Tags: tree, depth first search, binary tree

1026. Maximum Difference Between Node and Ancestor¶

LeetCode | LeetCode CH (Medium)
Tags: tree, depth first search, binary tree

3319. K-th Largest Perfect Subtree Size in Binary Tree¶

LeetCode | LeetCode CH (Medium)
Tags: tree, depth first search, sorting, binary tree

1339. Maximum Product of Splitted Binary Tree¶

LeetCode | LeetCode CH (Medium)
Tags: tree, depth first search, binary tree

1372. Longest ZigZag Path in a Binary Tree¶

LeetCode | LeetCode CH (Medium)
Tags: dynamic programming, tree, depth first search, binary tree

1145. Binary Tree Coloring Game¶

LeetCode | LeetCode CH (Medium)
Tags: tree, depth first search, binary tree

572. Subtree of Another Tree¶

LeetCode | LeetCode CH (Easy)
Tags: tree, depth first search, string matching, binary tree, hash function

572. Subtree of Another Tree - Python Solution

from typing import Optional

from binarytree import Node as TreeNode
from binarytree import build


# DFS - Tree
def isSubtree(root: Optional[TreeNode], subRoot: Optional[TreeNode]) -> bool:
    def isSameTree(p, q):
        if not p and not q:
            return True
        if not p or not q:
            return False
        if p.val != q.val:
            return False

        return isSameTree(p.left, q.left) and isSameTree(p.right, q.right)

    if not root:
        return False

    return (
        isSameTree(root, subRoot)
        or isSubtree(root.left, subRoot)
        or isSubtree(root.right, subRoot)
    )


# |------------|---------|----------|
# | Approach   | Time    | Space    |
# |------------|---------|----------|
# | DFS        | O(n * m)| O(n)     |
# |------------|---------|----------|


root = build([3, 4, 5, 1, 2, None, None, None, None, 0])
subRoot = build([4, 1, 2])
print(root)
#     ____3
#    /     \
#   4__     5
#  /   \
# 1     2
#      /
#     0
print(subRoot)
#   4
#  / \
# 1   2
print(isSubtree(root, subRoot))  # False

1530. Number of Good Leaf Nodes Pairs¶

LeetCode | LeetCode CH (Medium)
Tags: tree, depth first search, binary tree

298. Binary Tree Longest Consecutive Sequence¶

LeetCode | LeetCode CH (Medium)
Tags: tree, depth first search, binary tree

298. Binary Tree Longest Consecutive Sequence - Python Solution

from typing import Optional

from binarytree import Node as TreeNode
from binarytree import build


# Binary Tree
def longestConsecutive(root: Optional[TreeNode]) -> int:
    res = 0

    def dfs(node):
        if not node:
            return 0

        left, right = dfs(node.left), dfs(node.right)
        cur = 1
        if node.left and node.left.val == (node.val + 1):
            cur = max(cur, left + 1)
        if node.right and node.right.val == (node.val + 1):
            cur = max(cur, right + 1)

        nonlocal res
        res = max(res, cur)
        return cur

    dfs(root)

    return res


if __name__ == "__main__":
    root = build([1, 3, 2, 4, None, None, None, 5])
    print(root)
    #       1
    #      / \
    #     3   2
    #    /
    #   4
    #  /
    # 5
    print(longestConsecutive(root))  # 3

250. Count Univalue Subtrees¶

LeetCode | LeetCode CH (Medium)
Tags: tree, depth first search, binary tree

1973. Count Nodes Equal to Sum of Descendants¶

LeetCode | LeetCode CH (Medium)
Tags: tree, depth first search, binary tree

663. Equal Tree Partition¶

LeetCode | LeetCode CH (Medium)
Tags: tree, depth first search, binary tree

1120. Maximum Average Subtree¶

LeetCode | LeetCode CH (Medium)
Tags: tree, depth first search, binary tree

2792. Count Nodes That Are Great Enough¶

LeetCode | LeetCode CH (Hard)
Tags: divide and conquer, tree, depth first search, binary tree

333. Largest BST Subtree¶

LeetCode | LeetCode CH (Medium)
Tags: dynamic programming, tree, depth first search, binary search tree, binary tree

366. Find Leaves of Binary Tree¶

LeetCode | LeetCode CH (Medium)
Tags: tree, depth first search, binary tree

366. Find Leaves of Binary Tree - Python Solution

from collections import defaultdict
from typing import List, Optional

from binarytree import Node as TreeNode
from binarytree import build


def findLeaves(root: Optional[TreeNode]) -> List[List[int]]:
    depths = defaultdict(list)

    def dfs(node):
        if not node:
            return 0
        l, r = dfs(node.left), dfs(node.right)
        depth = 1 + max(l, r)
        depths[depth].append(node.val)
        return depth

    dfs(root)
    return [i for i in depths.values()]


if __name__ == "__main__":
    root = build([1, 2, 3, 4, 5])
    print(root)
    #     __1
    #    /   \
    #   2     3
    #  / \
    # 4   5
    print(findLeaves(root))  # [[4, 5, 3], [2], [1]]