Binary Tree Top-Down 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

112. Path Sum¶

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

112. Path Sum - 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 hasPathSum(root: Optional[TreeNode], targetSum: int) -> bool:
    if not root:
        return False

    if not root.left and not root.right:
        return root.val == targetSum

    targetSum -= root.val

    return hasPathSum(root.left, targetSum) or hasPathSum(
        root.right, targetSum
    )


root = build([5, 4, 8, 11, None, 13, 4, 7, 2, None, None, None, None, None, 1])
print(root)
#          5___
#         /    \
#     ___4     _8
#    /        /  \
#   11       13   4
#  /  \            \
# 7    2            1
print(hasPathSum(root, 22))  # True

129. Sum Root to Leaf Numbers¶

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

129. Sum Root to Leaf Numbers - Python Solution

from typing import Optional

from binarytree import Node as TreeNode
from binarytree import build


class Solution:
    def sumNumbers(self, root: Optional[TreeNode]) -> int:
        self.res = 0

        def dfs(node, cur):
            if not node:
                return
            cur = cur * 10 + node.val
            if not node.left and not node.right:
                self.res += cur
                return
            dfs(node.left, cur)
            dfs(node.right, cur)

        dfs(root, 0)

        return self.res


root = [1, 2, 3]
root = build(root)
print(root)
#   1
#  / \
# 2   3
print(Solution().sumNumbers(root))  # 25

199. Binary Tree Right Side View¶

LeetCode | LeetCode CH (Medium)

Tags: tree, depth first search, breadth first search, binary tree

    ____1       <---
   /     \
  2__     2     <--- Look at the rightmost node at each level
 /   \     \
3     4     3   <---
     /
    5           <---

199. Binary Tree Right Side View - Python Solution

from collections import deque
from typing import List, Optional

from binarytree import Node as TreeNode
from binarytree import build


# Binary Tree
def rightSideView(root: Optional[TreeNode]) -> List[int]:
    if not root:
        return []

    q = deque([root])
    res = []

    while q:
        n = len(q)
        for i in range(n):
            node = q.popleft()
            if i == n - 1:
                res.append(node.val)
            if node.left:
                q.append(node.left)
            if node.right:
                q.append(node.right)

    return res


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

1448. Count Good Nodes in Binary Tree¶

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

1448. Count Good Nodes in Binary Tree - Python Solution

from typing import List

from binarytree import Node as TreeNode
from binarytree import build


# Tree
def goodNodes(root: TreeNode) -> int:
    def dfs(node, max_val):
        if not node:
            return 0

        good = 1 if node.val >= max_val else 0

        max_val = max(max_val, node.val)

        good += dfs(node.left, max_val)
        good += dfs(node.right, max_val)

        return good

    return dfs(root, root.val)


root = build([3, 1, 4, 3, None, 1, 5])
print(root)
#     3__
#    /   \
#   1     4
#  /     / \
# 3     1   5
print(goodNodes(root))  # 4

1457. Pseudo-Palindromic Paths in a Binary Tree¶

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

1315. Sum of Nodes with Even-Valued Grandparent¶

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

988. Smallest String Starting From Leaf¶

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

1026. Maximum Difference Between Node and Ancestor¶

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

1022. Sum of Root To Leaf Binary Numbers¶

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

623. Add One Row to Tree¶

LeetCode | LeetCode CH (Medium)
Tags: tree, depth first search, breadth 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

971. Flip Binary Tree To Match Preorder Traversal¶

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

2689. Extract Kth Character From The Rope Tree¶

LeetCode | LeetCode CH (Easy)
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

1430. Check If a String Is a Valid Sequence from Root to Leaves Path in a Binary Tree¶

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

545. Boundary of Binary Tree¶

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