Binary Tree

Table of Contents

• 100. Same Tree
• 101. Symmetric Tree
• 104. Maximum Depth of Binary Tree
• 112. Path Sum
• 222. Count Complete Tree Nodes
• 226. Invert Binary Tree
• 257. Binary Tree Paths
• 530. Minimum Absolute Difference in BST
• 637. Average of Levels in Binary Tree

100. Same Tree

• LeetCode Link: Same Tree
• Difficulty: Easy
• Topic(s): Binary Tree, Depth-First Search, Breadth-First Search
• Company: Apple

🧠 Problem Statement

Given the roots of two binary trees p and q, write a function to check if they are the same or not.

Two binary trees are considered the same if they are structurally identical, and the nodes have the same value.

Example 1:

Input: p = [1,2,3], q = [1,2,3]
Output: true

Example 2:

Input: p = [1,2], q = [1,null,2]
Output: false

Example 3:

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

🧩 Approach

• DFS (Depth-First Search):
  • Recursively compare the nodes of both trees.
  • If both nodes are None, they are the same.
  • If one node is None and the other is not, they are different.
  • If the values of the nodes are different, they are different.
  • Recursively check the left and right subtrees.

💡 Solution

from typing import Optional

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


class Solution:
    def isSameTree(self, p: Optional[TreeNode], q: Optional[TreeNode]) -> bool:
        """
        Determine if two binary trees are the same.

        Args:
            p (Optional[TreeNode]): The root node of the first binary tree.
            q (Optional[TreeNode]): The root node of the second binary tree.

        Returns:
            bool: True if the two binary trees are the same, False otherwise.
        """
        def balanced(p: Optional[TreeNode], q: Optional[TreeNode]):
            """
            Helper function to determine if two binary trees are the same.
            Args:
                p (Optional[TreeNode]): The root node of the first binary tree.
                q (Optional[TreeNode]): The root node of the second binary tree.
            Returns:
                bool: True if the two binary trees are the same, False otherwise.
            """
            if not p and not q:
                return True

            if (p and not q) or (q and not p):
                return False

            if p.val != q.val:
                return False

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

        return balanced(p, q)

🧮 Complexity Analysis

• Time Complexity: O(n + m)
• Space Complexity: O(h_p + h_q)

101. Symmetric Tree

• LeetCode Link: Symmetric Tree
• Difficulty: Easy
• Topic(s): Binary Tree, Depth-First Search, Breadth-First Search
• Company: Apple

🧠 Problem Statement

Given the root of a binary tree, check whether it is a mirror of itself (i.e., symmetric around its center).

Example 1:

Input: root = [1,2,2,3,4,4,3]
Output: true

Example 2:

Input: root = [1,2,2,null,3,null,3]
Output: false

🧩 Approach

• DFS (Depth-First Search):
  • Recursively compare the left and right subtrees.
  • If both nodes are None, they are symmetric.
  • If one node is None and the other is not, they are not symmetric.
  • If the values of the nodes are different, they are not symmetric.
  • Recursively check the left subtree of one tree with the right subtree of the other tree and vice versa.

💡 Solution

from typing import Optional

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

class Solution:
    def isSymmetric(self, root: Optional[TreeNode]) -> bool:
        """
        Determine if a binary tree is symmetric.

        Args:
            root (Optional[TreeNode]): The root node of the binary tree.

        Returns:
            bool: True if the binary tree is symmetric, False otherwise.
        """
        def same(root1: Optional[TreeNode], root2: Optional[TreeNode]):
            """
            Helper function to determine if a binary tree is symmetric.

            Args:
                root1 (Optional[TreeNode]): The root node of the first subtree.
                root2 (Optional[TreeNode]): The root node of the second subtree.

            Returns:
                bool: True if the binary tree is symmetric, False otherwise.
            """
            if not root1 and not root2:
                return True

            if not root1 or not root2:
                return False

            if root1.val != root2.val:
                return False

            return same(root1.left, root2.right) and same(root1.right, root2.left)

        return same(root, root)

🧮 Complexity Analysis

• Time Complexity: O(n + m)
• Space Complexity: O(h_p + h_q)

104. Maximum Depth of Binary Tree

• LeetCode Link: Maximum Depth of Binary Tree
• Difficulty: Easy
• Topic(s): Binary Tree, Depth-First Search, Breadth-First Search
• Company: Microsoft

🧠 Problem Statement

Given the root of a binary tree, return its maximum depth.

A binary tree’s maximum depth is the number of nodes along the longest path from the root node down to the farthest leaf node.

Example 1:

Input: root = [3,9,20,null,null,15,7]
Output: 3

Example 2:

Input: root = [1,null,2]
Output: 2

🧩 Approach

• DFS (Depth-First Search):
  • Recursively calculate the depth of the left and right subtrees.
  • The maximum depth is 1 + max(depth of left subtree, depth of right subtree).

💡 Solution

from typing import Optional

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

class Solution:
    def maxDepth(self, root: Optional[TreeNode]) -> int:
        """
        Calculate the maximum depth of a binary tree.

        Args:
            root (Optional[TreeNode]): The root node of the binary tree.

        Returns:
            int: The maximum depth of the binary tree.
        """
        if not root:
            return 0

        return 1 + max(self.maxDepth(root.left), self.maxDepth(root.right))

🧮 Complexity Analysis

• Time Complexity: O(n)
• Space Complexity: O(h)

112. Path Sum

• LeetCode Link: Path Sum
• Difficulty: Easy
• Topic(s): Binary Tree, Depth-First Search, Breadth-First Search
• Company: Google

🧠 Problem Statement

Given the root of a binary tree and an integer targetSum, return true if the tree has a root-to-leaf path such that adding up all the values along the path equals targetSum.

A leaf is a node with no children.

Example 1:

Input: root = [5,4,8,11,null,13,4,7,2,null,null,null,1], targetSum = 22
Output: true
Explanation: The root-to-leaf path with the target sum is shown.

Example 2:

Input: root = [1,2,3], targetSum = 5
Output: false
Explanation: There are two root-to-leaf paths in the tree:
(1 --> 2): The sum is 3.
(1 --> 3): The sum is 4.
There is no root-to-leaf path with sum = 5.

Example 3:

Input: root = [], targetSum = 0
Output: false
Explanation: Since the tree is empty, there are no root-to-leaf paths.

🧩 Approach

• DFS (Depth-First Search):
  • Recursively traverse the tree, keeping track of the current sum.
  • If a leaf node is reached, check if the current sum equals the target sum.
  • Return true if a valid path is found, otherwise return false.

💡 Solution

from typing import Optional

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

class Solution:
    def hasPathSum(self, root: Optional[TreeNode], targetSum: int) -> bool:
        """
        Determine if the binary tree has a root-to-leaf path with the given sum.

        Args:
            root (Optional[TreeNode]): The root node of the binary tree.
            targetSum (int): The target sum to check for.

        Returns:
            bool: True if the binary tree has a root-to-leaf path with the given sum, False otherwise.
        """
        def hasSum(root: Optional[TreeNode], cur_sum: int) -> bool:
            """
            Helper function to determine if the binary tree has a root-to-leaf path with the given sum.

            Args:
                root (Optional[TreeNode]): The current node of the binary tree.
                cur_sum (int): The current sum of the path.

            Returns:
                bool: True if the binary tree has a root-to-leaf path with the given sum, False otherwise.
            """
            if not root:
                return False

            cur_sum += root.val

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

            return hasSum(root.left, cur_sum) or hasSum(root.right, cur_sum)

        return hasSum(root, 0)

🧮 Complexity Analysis

• Time Complexity: O(n)
• Space Complexity: O(h)

222. Count Complete Tree Nodes

• LeetCode Link: Count Complete Tree Nodes
• Difficulty: Medium
• Topic(s): Binary Tree, Depth-First Search, Breadth-First Search
• Company: Amazon

🧠 Problem Statement

Given the root of a complete binary tree, return the number of the nodes in the tree.

According to Wikipedia, every level, except possibly the last, is completely filled in a complete binary tree, and all nodes in the last level are as far left as possible. It can have between 1 and 2^h nodes inclusive at the last level h.

Design an algorithm that runs in less than O(n) time complexity.

Example 1:

Input: root = [1,2,3,4,5,6]
Output: 6

Example 2:

Input: root = []
Output: 0

Example 3:

Input: root = [1]
Output: 1

🧩 Approach

• DFS (Depth-First Search):
  • Recursively count the nodes in the left and right subtrees.
  • The total number of nodes is 1 + count of left subtree + count of right subtree.

💡 Solution

from typing import Optional

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

class Solution:
    def countNodes(self, root: Optional[TreeNode]) -> int:
        """
        Count the number of nodes in a complete binary tree.

        Args:
            root (Optional[TreeNode]): The root node of the complete binary tree.

        Returns:
            int: The number of nodes in the complete binary tree.
        """
        if not root:
            return 0

        return 1 + self.countNodes(root.left) + self.countNodes(root.right)

🧮 Complexity Analysis

• Time Complexity: O(n)
• Space Complexity: O(h)

226. Invert Binary Tree

• LeetCode Link: Invert Binary Tree
• Difficulty: Easy
• Topic(s): Binary Tree, Depth-First Search, Breadth-First Search
• Company: Microsoft

🧠 Problem Statement

Given the root of a binary tree, invert the tree, and return its root.

Example 1:

Input: root = [4,2,7,1,3,6,9]
Output: [4,7,2,9,6,3,1]

Example 2:

Input: root = [2,1,3]
Output: [2,3,1]

Example 3:

Input: root = []
Output: []

🧩 Approach

• DFS (Depth-First Search):
  • Recursively swap the left and right children of each node.
  • Return the root of the inverted tree.

💡 Solution

from typing import Optional

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

class Solution:
    def invertTree(self, root: Optional[TreeNode]) -> Optional[TreeNode]:
        """
        Invert a binary tree.

        Args:
            root (Optional[TreeNode]): The root node of the binary tree.

        Returns:
            Optional[TreeNode]: The root node of the inverted binary tree.
        """
        if not root:
            return None

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

        self.invertTree(root.left)
        self.invertTree(root.right)

        return root

🧮 Complexity Analysis

• Time Complexity: O(n)
• Space Complexity: O(h)

257. Binary Tree Paths

• LeetCode Link: Binary Tree Paths
• Difficulty: Easy
• Topic(s): Binary Tree, Depth-First Search, Backtracking
• Company: Capital One

🧠 Problem Statement

Given the root of a binary tree, return all root-to-leaf paths in any order.

A leaf is a node with no children.

Example 1:

Input: root = [1,2,3,null,5]
Output: ["1->2->5","1->3"]

Example 2:

Input: root = [1]
Output: ["1"]

🧩 Approach

1. Use Depth-First Search (DFS) to traverse the tree.
2. Maintain the current path as a string.
3. When a leaf node is reached, add the current path to the result list.
4. Call the DFS function recursively for left and right children.

💡 Solution

from typing import Optional, List

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

class Solution:
    def binaryTreePaths(self, root: Optional[TreeNode]) -> List[str]:
        """
        Find all root-to-leaf paths in a binary tree.

        Args:
            root (Optional[TreeNode]): The root node of the binary tree.

        Returns:
            List[str]: A list of strings representing all root-to-leaf paths.
        """
        def dfs(root: Optional[TreeNode], path: str) -> None:
            """
            Helper function to perform DFS and find all root-to-leaf paths.

            Args:
                root (Optional[TreeNode]): The current node of the binary tree.
                path (str): The current path from the root to the current node.
            """
            if root:
                path += str(root.val)
                if not root.left and not root.right:
                    paths.append(path)
                else:
                    path += "->"
                    dfs(root.left, path)
                    dfs(root.right, path)

        paths: List[str] = []
        dfs(root, "")
        return paths

🧮 Complexity Analysis

• Time Complexity: O(n)
• Space Complexity: O(h)

530. Minimum Absolute Difference in BST

• LeetCode Link: Minimum Absolute Difference in BST
• Difficulty: Easy
• Topic(s): Binary Search Tree, Depth-First Search, Inorder Traversal
• Company: Meta

🧠 Problem Statement

Given the root of a Binary Search Tree (BST), return the minimum absolute difference between the values of any two different nodes in the tree.

Example 1:

Input: root = [4,2,6,1,3]
Output: 1

Example 2:

Input: root = [1,0,48,null,null,12,49]
Output: 1

🧩 Approach

• Inorder Traversal:
  • Perform an inorder traversal of the BST to get the node values in sorted order.
  • Keep track of the previous node value and calculate the minimum difference between the current and previous node values.

💡 Solution

from typing import Optional, List

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

class Solution:
    def getMinimumDifference(self, root: Optional[TreeNode]) -> int:
        """
        Find the minimum absolute difference between values of any two different nodes in a BST.

        Args:
            root (Optional[TreeNode]): The root node of the binary search tree.

        Returns:
            int: The minimum absolute difference between values of any two different nodes in the BST.
        """
        min_distance: List[int] = [float("inf")]
        prev: List[int] = [None]

        def dfs(node: Optional[TreeNode]):
            if not node:
                return None

            dfs(node.left)

            if prev[0] is not None:
                min_distance[0] = min(min_distance[0], node.val - prev[0])

            prev[0] = node.val

            dfs(node.right)

        dfs(root)
        return min_distance[0]

🧮 Complexity Analysis

• Time Complexity: O(n)
• Space Complexity: O(h)

637. Average of Levels in Binary Tree

• LeetCode Link: Average of Levels in Binary Tree
• Difficulty: Easy
• Topic(s): Binary Tree, Breadth-First Search
• Company: Amazon

🧠 Problem Statement

Given the root of a binary tree, return the average value of the nodes on each level in the form of an array. Answers within 10^-5 of the actual answer will be accepted.

Example 1:

Input: root = [3,9,20,null,null,15,7]
Output: [3.00000,14.50000,11.00000]
Explanation: The average value of nodes on level 0 is 3, on level 1 is 14.5, and on level 2 is 11.
Hence return [3, 14.5, 11].

Example 2:

Input: root = [3,9,20,15,7]
Output: [3.00000,14.50000,11.00000]

🧩 Approach

• BFS (Breadth-First Search):
  • Use a queue to traverse the tree level by level.
  • For each level, calculate the sum of the node values and the number of nodes.
  • Compute the average for each level and store it in a result list.

💡 Solution

from typing import Optional, Deque, List
from collections import deque

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


class Solution:
    def averageOfLevels(self, root: Optional[TreeNode]) -> List[float]:
        """
        Calculate the average value of nodes on each level of a binary tree.

        Args:
            root (Optional[TreeNode]): The root node of the binary tree.

        Returns:
            List[float]: A list of average values for each level of the binary tree.
        """
        avgs: List[float] = []
        q: Deque[TreeNode] = deque()
        q.append(root)

        while q:
            avg = 0
            n: int = len(q)
            for _ in range(n):
                node: Optional[TreeNode] = q.popleft()
                avg += node.val

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

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

            avg /= n
            avgs.append(avg)

        return avgs

🧮 Complexity Analysis

• Time Complexity: O(n)
• Space Complexity: O(n)