Binary Tree

Binary Tree Traversal

The example code node definitions

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

Example Problems

• 94. Binary Tree Inorder Traversal
• 144. Binary Tree Preorder Traversal
• 145. Binary Tree Postorder Traversal
• 102. Binary Tree Level Order Traversal

Tips of Binary Tree Problem

Resolve Top Down

1. End case, return null from leaf node
2. Update the answer
3. left = top_down(node.left, params)
4. right = top_down(node.right, params)
5. return the answer

Resolve Bottom Up

1. End case, return null from leaf node
2. left = bottom_up(node.left)
3. right = bottom_up(node.right)
4. return answers

Binary Tree Problems

Maximum Depth of Binary Tree

Leetcode Link

class Solution:
    def maxDepth(self, root: Optional[TreeNode]) -> int:
        if not root:
            return 0
        return self._travel(0, root)

    def _travel(self, deepth: int, node) -> int:
        if not node:
            return deepth
        return max(self._travel(deepth+1, node.left), self._travel(deepth+1, node.right))

Symmetric Tree

Leetcode Link

class Solution:
    def isSymmetric(self, root: Optional[TreeNode]) -> bool:
        if not root:
            return False
        return self._equal(root.left, root.right)

    def _equal(self, left: Optional[TreeNode], right: Optional[TreeNode]) -> bool:
        if not left and not right:
            return True

        if not left or not right:
            return False

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

        return self._equal(left.left, right.right) and self._equal(left.right, right.left)

Path Sum

Leetcode Link

class Solution:
    def hasPathSum(self, root: Optional[TreeNode], targetSum: int) -> bool:
        return self._travel(0, root, targetSum)

    def _travel(self, total: int, node: Optional[TreeNode], targetSum: int) -> bool:
        if not node:
            return False

        if not node.left and not node.right and total + node.val == targetSum:
            return True

        return self._travel(total+node.val, node.left, targetSum) \
            or self._travel(total+node.val, node.right, targetSum)

Count Univalue Subtrees

Leetcode Link