LeetCode: Trees

Published: August 5, 2025Updated: August 5, 2025

69 min read

#data structures and algorithms

Table Of Content

Tree Intro
226. Invert Binary Tree ::3:: - Easy
104. Maximum Depth of Binary Tree ::4:: - Easy
543. Diameter of Binary Tree ::2:: - Easy
110. Balanced Binary Tree ::2:: - Easy
100. Same Tree ::2:: - Easy
572. Subtree of Another Tree ::5:: - Easy
235. Lowest Common Ancestor of a Binary Search Tree ::2:: - Medium
102. Binary Tree Level Order Traversal ::2:: - Medium
199. Binary Tree Right Side View ::2:: - Medium
1448. Count Good Nodes in Binary Tree ::2:: - Medium
98. Validate Binary Search Tree ::2:: - Medium
230. Kth Smallest Element in a BST ::2:: - Medium
105. Construct Binary Tree from Pre Order and In Order Traversal ::2:: - Medium
124. Binary Tree Maximum Path Sum ::1:: - Hard
297. Serialize and Deserialize Binary Tree ::2:: - Hard

Tree Intro

What is a Tree

Trees are hierarchical data structures representing relationships between entities, often in a parent-child format.

Tree Characteristics

Trees are a special type of graph, characterized by:

Nodes: The entities (ex: values, objects)
Edges: The connections between the entities. A tree with n nodes has n - 1 edges.
Root: The top-most node, with no parent
Leaves: Nodes with no children
Height: The number of edges on the longest path from the root to a leaf
Depth: The number of edges from the root to a specific node
No Cycles: Trees do not contain cycles
Single Paths: Trees have exactly one path between any two nodes

Tree Representations

Trees can be represented in multiple formats:

Adjacency Matrix: Used for general trees or graphs
Parent Array: Store each child -> parent, in an array
Linked Node Structure: Common in Binary Trees (TreeNode with left and right)

For full notes on representations: please see graph representations

Tree Math

Height of a perfect binary tree with n nodes: log(n+1)-1

Nodes in perfect binary tree of height h: 2^(h+1) -1

Max nodes at level l: 2^l

Edges = Nodes - 1

Common Tree Types

Binary Tree: Each node has at most two children left and right. Most LeetCode problems use this form.
Binary Search Tree (BST): Type of binary tree where: Left subtree val < Node val < Right subtree val

Allows efficient search, insertion, and deletion.

Balanced Binary Tree (AVL, Red-Black) Type of binary tree where: Height difference (balance factor) is kept small, ensuring the height stays O(log n).

This prevents BST from degrading to a linked list in worst case

Complete Binary Tree Type of binary tree where: All levels are filled except possibly the last, which is filled from left to right.
Full Binary Tree Type of binary tree where: Each node has either 0 or 2 children
Perfect Binary Tree Type of binary tree where: All internal nodes have 2 children and all leaves are at the same level.
N-ary Tree Type of tree where: Each node can have up to N children

Balanced Trees

Balanced trees are binary search trees that maintain their height close to O(log n) by rebalancing themselves during insertion() and deletion().

Without balancing, a BST can degrade to a linked list: height(O(n)) if the elements are inserted in sorted order

This is done by limiting the height difference (balance factor) between left and right subtrees.

Common Balanced Trees:

AVL Tree: Strict balancing. Balance factor at each node is in [-1, 0, 1]. Rotations restore balance after insert/delete
Red Black Tree: Looser balancing with colour properties. Guarantees height ≤ 2 * log(n+1)
B- Trees / B+ Trees: Multi way balanced trees used in databases and filesystems for efficient range queries

Operation	BST (Unbalanced)	Balanced BST
Search	O(n)	O(log n)
Insert/Delete	O(n)	O(log n)

Tree Traversal Overview

Given a Tree, and the task to traverse it, there a two fundamental search strategies that all others stem from.

Depth First Search Traversal (DFS)

Traversal Order: Goes as deep as possible before backtracking (either recursively via function calls or iteratively via stack)

Can process in pre, in, or post order:

Pre: Root -> Left -> Right

In: Left -> Root -> Right

Post: Left -> Right -> Root

Breadth First Search Traversal (BFS)

Traversal Order: Explores nodes level by level

Will queue nodes for next level, count how many exist, and process all nodes for that level by iterating exactly level_size times popping each from the queue, thus popping all nodes for a specific level.

Specialized Traversals

Morris Traversal: In order traversal with O(1) extra space by temporarily modifying tree pointers.
Threaded Binary Tree: Uses null child pointers to store predecessor/successor pointers to enable O(1) traversal.

Tree Search Rule of Thumb

Pre, In, Post, order traversal -> DFS (recursive usually, iterative stack based)

Level Order Traversal -> BFS (iterative) queue based

Tree Application: DFS Pre Order Recursive One Sided Top Down

Traversal Order: Root -> Left -> Right (or Root -> Right -> Left) Mindset: Process the root as soon as you see it, then traverse into one subtree fully before the other Trick: I'll visit you first, then i'll deal with your kids

Ex: Serialize a Binary Tree Recursive

    def preOrderSerializeRecursive(root: Optional[TreeNode]) -> str:
        
        def dfsPreOrder(node):
            # Note:
            # DFS pre order: root -> left -> right

            # Base case: process leaf 
            if not node:
                vals.append("N")
                return
            
            # Process root -> (DFS top down)
            vals.append(str(node.val))
            
            # Note:
            # order of recursive call determines order

            # Recursive call to process -> left -> right, left deepest 
            dfsPreOrder(node.left)
            dfsPreOrder(node.right)

            # could have been: -> right -> left
            # with deep right subtree 
            # dfsPreOrder(node.right)
            # dfsPreOrder(node.left)
        
        # serialized array
        vals = []

        # recursive call at root
        dfsPreOrder(root)

        # join serialized array
        return ",".join(vals)

    # Tree:
    #       1
    #      / \
    #     2   3
    #        / \
    #       4   5
    # Output: "1,2,N,N,3,4,N,N,5,N,N"

Tree Application: DFS Pre Order Iterative One Sided Top Down

Ex: Pre Order Serialize a Binary Tree Iterative

    def preOrderSerializeIterative(root: Optional[TreeNode]) -> str:
        # Note:
        # DFS pre order: root -> left -> right

        # Empty Check
        if not root:
            return "N"

        # iteration via stack
        stack = [root]

        # serialized array
        vals = []
        
        while stack:

            # dfs -> pop()
            # bfs -> popleft()
            currRoot = stack.pop()

            # process root ->: if value
            if currRoot:

                # serialize root (dfs pre order top down)
                vals.append(str(currRoot.val))
                
                # Note:
                # order of append determines order

                # Iterative process: -> left -> right
                # append(right), append(left), as pop() will pop(left), pop(right)
                # pop() leads to deep left subtree search 
                stack.append(currRoot.right)
                stack.append(currRoot.left)


                # Could have been -> right -> left
                # leading to deep right subtree search
                # stack.append(currRoot.left)
                # stack.append(currRoot.right)
            
            # process root ->: if leaf
            else:
                # serialize root (dfs pre order top down)
                vals.append("N")
        
        # join serialized array
        return ",".join(vals)

    # Tree:
    #       1
    #      / \
    #     2   3
    #        / \
    #       4   5
    # Output: "1,2,N,N,3,4,N,N,5,N,N"

Tree Application: DFS In Order Recursive One Sided Bottom Up

Traversal Order: Left -> Root -> Right (or Right -> Root -> Left) Mindset: Fully explore one side before paying attention to the root, then move to the other side Trick: I'll finish everything to your left or right before I pay attention to you

Ex: Convert BST to Sorted List Recursive and Validate BST Iterative

    def bstToSortedList(root: Optional[TreeNode]) -> List[int]:
        
        # tracks previous value
        prev_val = float("-inf")
            
        def dfsInOrder(node):
            nonlocal prev_val
            
            # Base case: leaf -> no value
            if not node:
                return True
            
            # recursive call to process left subtree
            if not dfsInOrder(node.left):
                return False
            
            # process node (mid-point work)
            if node.val <= prev_val:
                return False

            # set to current value
            prev_val = node.val
            
            # recursive call to process right subtree
            return dfsInOrder(node.right)
        
        # recursive call on root
        return dfsInOrder(root)

        # Tree:
        #       2
        #      / \
        #     1   3
        # isValidBST -> True

Tree Application: DFS In Order Iterative One Sided Bottom Up

Ex: Convert BST to Sorted List Recursive and Validate BST Iterative

    def isValidBST(root: Optional[TreeNode]) -> bool:
        
        # tracks previous value
        prev_val = float("-inf")

        # iteration via stack
        stack = [] 

        # pointer to check for empty case
        curr = root
        
        while stack or curr:
            
            # traverse left subtree of curr:
            # will go as far left as possible
            while curr: 
                # continue traversal down left subtree
                stack.append(curr)
                curr = curr.left
            
            # Exited loop: 
            # reached 'leaf' of left subtree
            #     L
            #  /     \ 
            # leaf    ?
                        
            # process left, node, right:
            # via previous left subtree node 'L' from stack
            curr = stack.pop()

            # validate
            if curr.val <= prev_val:
                return False

            # set to current value
            prev_val = curr.val
            
            # traverse right subtree
            # (which we thus explore left, node and right subtrees again)
            #     L
            #  /     \ 
            # leaf    *here*
            curr = curr.right
        
        return True

    # Tree:
    #       2
    #      / \
    #     1   3
    # isValidBST -> True

Tree Application: DFS Post Order Recursive Two Sided Bottom Up

Traversal Order: Left -> Right -> Root (or Right -> Left -> Root) Mindset: Fully explore both sides before processing the root. Trick: I'll finish everything to your left then right or right then left before I pay attention to you

Ex: Evaluate Expression Tree Recursive and Delete Tree Iterative

    def diameterOfBinaryTree(root: Optional[TreeNode]) -> int:
        
        # global diameter
        diameter = 0

        def dfs(node):
            nonlocal diameter

            # Base case:
            # no width added
            if not node:
                return 0

            # recursive call to process left and right
            left = dfs(node.left)
            right = dfs(node.right)

            # process node
            diameter = max(diameter, left + right)

            # pass width upwards
            return 1 + max(left, right)

        # recursive on root
        dfs(root)

        # return global diameter
        return diameter

    # Tree:
    #         1
    #        / \
    #       2   3
    #      / \
    #     4   5
    # diameterOfBinaryTree -> 3

Tree Application: DFS Post Order Iterative Two Sided Bottom Up

Ex: Evaluate Expression Tree Recursive and Delete Tree Iterative

    def diameterOfBinaryTree(root: Optional[TreeNode]) -> int:

        # Empty check
        if not root:
            return 0

        # global width
        diameter = 0

        # iterative stack
        stack = []

        # 
        curr = root
        lastVisited = None
        depth_map = defaultdict(int)

        while stack or curr:

            # traverse left subtree of curr:
            # will go as far left as possible
            while curr:
                stack.append(curr)
                curr = curr.left

            # check if right subtree exists
            peek = stack[-1]

            # if right subtree exists and hasn't been visited
            if peek.right and lastVisited != peek.right:
                node = peek.right

            # process node
            else:
                stack.pop()

                # grab width of left and right subtree if exists
                left_depth = depth_map.get(peek.left, 0)
                right_depth = depth_map.get(peek.right, 0)

                # node diameter
                diameter = max(diameter, left_depth + right_depth)

                # store node diameter
                depth_map[peek] = 1 + max(left_depth, right_depth)

                # set last visited to current node
                lastVisited = peek

        # return width
        return diameter

    # Tree:
    #         1
    #        / \
    #       2   3
    #      / \
    #     4   5
    # diameterOfBinaryTree -> 3 (path: 4 → 2 → 5 or 4 → 2 → 1 → 3)

Tree Application: BFS Pre Order Across Level For Level Size Based Grouping Full Across Top Down

Traversal Order: Level by Level BFS visits nodes level by level, processing all nodes at a given depth before moving on to the next. Used for level order problems and shortest path calculations in unweighted graphs, as well as scenarios requiring nodes in order of distance from the root.

Ex: Level order traversal of Binary Tree

    def levelOrderIterative(root: Optional[TreeNode]) -> List[List[int]]:
        
        # Empty check
        if not root:
            return []

        group = []

        # start with group 1: root
        queue = deque([root])

        while queue:

            # grab size of curr level
            size = len(queue)
            level = []

            # process entire level
            for _ in range(size):

                # grab node of group
                node = queue.popleft()
                level.append(node.val)

                # append next level
                if node.left:
                    queue.append(node.left)
                if node.right:
                    queue.append(node.right)

            # add level group to list of groups
            groups.append(level)

        # return all level groups
        return groups

    # Example:
    # Input Tree:
    #       1
    #      / \
    #     2   3
    #        / \
    #       4   5
    # Output: [[1], [2, 3], [4, 5]]

Tree Application: BFS Pre Order Across Level No Explicit Level Sized Grouping Full Across Top Down

Traversal Order: Level by Level BFS visit nodes in breath first order. However, in some problems we don't process or store the full level at once. Instead we act on nodes individually or in partial groupings (pairs, linked neighbors, etc)

Ex: Invert a Binary Tree

    def invertTree(root: Optional[TreeNode]) -> Optional[TreeNode]:
        if not root:
            return None

        # start at root
        queue = deque([root])
        
        while queue:

            # grab nodes sequentially
            node = queue.popleft()
            
            # process node
            node.left, node.right = node.right, node.left
            
            # process left and right subtrees by appending to queue
            if node.left:
                queue.append(node.left)
            if node.right:
                queue.append(node.right)
        
        return root

        # Example:
        # Input Tree:
        #       4
        #      / \
        #     2   7

        # Output Tree:
        #       4
        #      / \
        #     7   2

Tree Application: BFS Pre Order Across Level Distance from Root Full Across Top Down

Traversal Order: Level by Level Distance Tracking: Each level corresponds to one distance step from the root. Used when the problem depends on minimum, maximum or some count depth.

Ex: Minimum Depth of a Binary Tree

    def minDepth(root: Optional[TreeNode]) -> int:
        from collections import deque
        
        # Empty Tree
        if not root:
            return 0
        
        # initialize depth value
        queue = deque([(root, 1)])
        
        while queue:
            
            # grab current depth, increase to children
            node, depth = queue.popleft()
            
            # first leaf found -> min depth 
            if not node.left and not node.right:
                return depth
            
            # iterate to left and right subtrees with updated depth
            if node.left:
                queue.append((node.left, depth + 1))
            if node.right:
                queue.append((node.right, depth + 1))

Tree Application: BFS Pre Order Across Level Non-Standard Level Traversal Non Standard Full Across

Traversal Order: Level by Level (but with non default ordering such as reversed, zigzag, or other patterns) Used when the traversal order of nodes at each level must follow a specific non standard pattern

Ex: Binary Tree Zigzag Level Order Traversal

    def zigzagLevelOrder(root: Optional[TreeNode]) -> List[List[int]]:
        
        # Empty Tree
        if not root:
            return []
        
        groups = []

        # iteration stack
        queue = deque([root])

        # order toggle
        left_to_right = True
        
        while queue:

            # for each level
            size = len(queue)
            level = deque()
            
            # Process all nodes in current level
            for _ in range(size):
                node = queue.popleft()
                
                # append order based on pattern
                if left_to_right:
                    level.append(node.val)
                else:
                    level.appendleft(node.val)
                
                # iterate by appending left and right subtrees
                if node.left:
                    queue.append(node.left)
                if node.right:
                    queue.append(node.right)
            
            # flip order for next level
            left_to_right = not left_to_right  

            # add to groups            
            groups.append(list(level))

        return groups

    # Example:
    # Input Tree:
    #       1
    #      / \
    #     2   3
    #    / \   \
    #   4   5   6

    # Output: [[1], [3, 2], [4, 5, 6]]

Tree Application: BST Guided Recursive Traversal

Traversal Order: Top down traversal pruning half the tree at each step based on BST property Mindset: Use BST ordering to decide which subtree to recurse into Trick: Like binary search, narrow search space by recursively exploring only one subtree.

Ex: Lowest Common Ancestor in BST Recursive

    def lowestCommonAncestor(root: TreeNode, p: TreeNode, q: TreeNode) -> TreeNode:
    
        # If both nodes smaller than root, recurse left subtree
        if p.val < root.val and q.val < root.val:
            return lowestCommonAncestor(root.left, p, q)

        # If both nodes greater than root, recurse right subtree
        elif p.val > root.val and q.val > root.val:
            return lowestCommonAncestor(root.right, p, q)
        
        # Otherwise, root is split point and LCA
        else:
            return root

Tree Application: BST Guided Iterative Traversal

Traversal Order: Top down traversal pruning half the tree at each step based on BST property Mindset: Use BST ordering to decide which subtree to iterate into Trick: Like binary search, narrow search space by iteratively exploring only one subtree.

Ex: Lowest Common Ancestor in BST Iterative

    def lowestCommonAncestor(root: TreeNode, p: TreeNode, q: TreeNode) -> TreeNode:
        curr = root

        while curr:
            # If both nodes smaller, go left
            if p.val < curr.val and q.val < curr.val:
                curr = curr.left

            # If both nodes greater, go right
            elif p.val > curr.val and q.val > curr.val:
                curr = curr.right
            
            # Else, current node is LCA
            else:
                return curr

226. Invert Binary Tree ::3:: - Easy

Topics: Tree, Depth First Search, Breadth First Search, Binary Tree

Intro

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

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

Constraints:

The number of nodes in the tree is in the range [0, 100]

-100 ≤ Node.val ≤ 100

Abstraction

Invert the binary tree.

Space & Time Complexity

Solution	Time Complexity	Space Complexity	Time Remark	Space Remark

Bug	Error

Brute Force:

Aspect	Time Complexity	Space Complexity	Time Remarks	Space Remarks

Find the Bug:

Solution 1: DFS Post Order Recursive Pass Up Inverted Subtrees - Tree/DFS Post Order Recursive Two Sided Bottom Up

    def invertTree(self, root: Optional[TreeNode]) -> Optional[TreeNode]:
        # Note:
        # DFS post order: left -> right -> root
        # 1. Process left -> right: inverting
        # 2. Process  -> root: swap left and right subtree
        # Result: swapping bottom to up 

        # Base case: no swap
        if not root:
            return None

        # Recursive call to process left -> right subtrees
        left_inverted = self.invertTree(root.left)
        right_inverted = self.invertTree(root.right)

        # Could have been: right -> left subtrees
        # right_inverted = self.invertTree(root.right)
        # left_inverted = self.invertTree(root.left)

        # Process -> root: swap left and right subtrees
        root.left = right_inverted
        root.right = left_inverted

        # pass inverted root to parent

        # overall: time complexity O(n)
        # overall: space complexity O(h), O(log n) for balanced tree
        return root

Solution 2: DFS Post Order Iterative Carry Up Inverted Subtrees - Tree/DFS Post Order Recursive Two Sided Bottom Up

    def invertTree(self, root: Optional[TreeNode]) -> Optional[TreeNode]:
        # Note:
        # DFS post order: left -> right -> root
        # 1. Process left -> right: inverting
        # 2. Process  -> root: swap left and right subtree
        # Result: swapping bottom to up 

        if not root:
            return None

        stack = []

        # current pointer
        curr = root

        # last visited
        lastVisitde = None 

        while stack or curr:

            # process -> left : 
            # traverse left subtree of root 
            while curr: 
                stack.append(curr)
                curr = curr.left

            # check if right subtree exists
            peek = stack[-1]

            # process  -> right : 
            # if right subtree exists and has not been visited: 
            # (remember: left subtree of right subtree will be traversed first)
            if peek.right and lastVisited != peek.right:
                curr = peek.right
            
            # process -> root : (after both subtrees)
            else:
                stack.pop()

                # process node
                peek.left, peek.right = peek.right, peek.left

                # last visited set to curr
                lastVisited = peek

        return root

Solution 3: BFS Pre Order Iterative Full Level Node Inversion - Tree/BFS Pre Order Across Level For Level Size Based Grouping Full Across Top Down

    def invertTree(self, root: Optional[TreeNode]) -> Optional[TreeNode]:
        # Note:
        # BFS iterative: level by level: root -> left -> right
        # 1. Process root -> : iterate over level
        #      swap left and right subtrees
        # 2. Process -> left -> right: append left and right iterative process
        # Result: Top down invert
        
        # Empty check
        if not root:
            return None
        
        # iterative level stack:
        queue = deque([root])
        
        while queue:

            # current level length 
            size = len(queue)

            # process full level at a time
            for _ in range(size):

                # process root -> :
                node = queue.popleft()
                
                # process root -> : swap left and right subtrees
                node.left, node.right = node.right, node.left
                
                # process -> left -> right subtrees
                if node.left:
                    queue.append(node.left)
                if node.right:
                    queue.append(node.right)
        
        # overall: time complexity O(n)
        # overall: space complexity O(n)
        return root

Aspect	Time Complexity	Space Complexity	Time Remarks	Space Remarks

104. Maximum Depth of Binary Tree ::4:: - Easy

Topics: Tree, Depth First Search, Breadth First Search, Binary Tree

Intro

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 Input	Output
root = [3,9,20,null,null,15,7]	3
root = [1,null,2]	2

Constraints:

The number of nodes in the tree is in the range [0, 10⁴]

-100 ≤ Node.val ≤ 100

Abstraction

Find the max depth of a binary tree.

Space & Time Complexity

Solution	Time Complexity	Space Complexity	Time Remark	Space Remark

Bug	Error

Brute Force:

Aspect	Time Complexity	Space Complexity	Time Remarks	Space Remarks

Find the Bug:

Solution 1: DFS Post Order Recursive Pass Up Subtree Depth - Tree/DFS Post Order Recursive Two Sided Bottom Up

    def maxDepth(self, root: Optional[TreeNode]) -> int:
        # Note:
        # DFS post order traversal: left -> right -> root
        # 1. Process left -> right
        # 2. Process -> root : by max(left_subtree, right_subtree)
        # Result: max depth of tree
        
        # Base case:
        # leaf -> depth of 0
        if not root:
            return 0
        
        # process left -> right ->
        left_depth = self.maxDepth(root.left)
        right_depth = self.maxDepth(root.right)
        
        # could have been: right -> left ->
        # right_depth = self.maxDepth(root.right)
        # left_depth = self.maxDepth(root.left)

        # process -> root
        root_depth = 1 + max(left_depth, right_depth)

        return root_depth

Aspect	Time Complexity	Space Complexity	Time Remarks	Space Remarks

Solution 2: DFS Post Order Iterative Dictionary (Lookup Subtree Depth) - Tree/DFS Post Order Iterative Two Sided Bottom Up

    def maxDepth(self, root: Optional[TreeNode]) -> int:
        # Note:
        # DFS post order traversal: left -> right -> root
        # 1. Process left -> right: subtrees
        # 2. Process -> root: by max(left_subtree, right_subtree)
        # Result: max depth of tree
        
        if not root:
            return 0

        stack = []
        depth_map = defaultdict(int)
        curr = root
        last_visited = None

        while stack or curr:
            
            # process left ->
            while curr:
                stack.append(curr)
                curr = curr.left
            
            # check if -> right : exists
            peek = stack[-1]

            # Process -> right : 
            # if right child exists and hasn't been processed yet
            if peek.right and last_visited != peek.right:
                curr = peek.right

            # Process -> root : 
            else:
                # remove root from stack
                stack.pop()
                
                # grab left and right results from dictionary
                left_depth = depth_map[peek.left]
                right_depth = depth_map[peek.right]

                # Process -> root : 
                current_depth = 1 + max(left_depth, right_depth)

                # Process -> root :
                depth_map[peek] = current_depth

                # update last visited
                last_visited = peek

        # overall: time complexity
        # overall: space complexity
        return depth_map[root]

Solution 3: DFS Pre Order Iterative Global Depth + Tuple (Subtree, Subtree Depth) Pass Down - Tree/DFS Pre Order Iterative One Sided Top Down

    # Note:
    # DFS pre order iterative: root -> left -> right
    # 1. Process root -> : root depth vs max_depth, append subtrees + 1 root depth
    # 2. Process -> left -> right :
    # Result: deepest branch updates global max_depth
    
    # Empty check
    if not root:
        return 0
    
    # iterative level stack
    stack = [(root, 1)]

    # global depth
    max_depth = 0
    
    while stack:

        # process entire level
        size = len(stack)
        for _ in range(size):

            # process root -> : (node, node_depth)
            node, node_depth = stack.popleft()
            
            # process root -> : max_depth vs node_depth
            max_depth = max(max_depth, node_depth)
            
            # process -> left -> right : depth by + 1
            if node.left:
                stack.append((node.left, node_depth + 1))
            if node.right:
                stack.append((node.right, node_depth + 1))
    
    # overall: time complexity
    # overall: space complexity
    return max_depth

Solution 4: BFS Pre Order Iterative Full Level Global Depth + Completed Level Adds to Depth - Tree/BFS Pre Order Across Level For Level Size Based Grouping Full Across Top Down

    def maxDepth(self, root: Optional[TreeNode]) -> int:
        # Note:
        # BFS pre order iterative: process level by: root -> left -> right
        # 1. For each level: get len of level
        # 2. Process root -> 
        # 3. Process -> left -> right
        # Result: depth is total of levels -> max depth 
        
        # Empty check
        if not root:
            return 0
        
        # iterative stack
        queue = deque([root])

        # global depth
        depth = 0
        
        while queue:

            # level size
            size = len(queue)

            # process all nodes in current level
            for _ in range(size):

                # pop() all nodes
                node = queue.popleft()

                # append() subtrees belonging to next level
                if node.left:
                    queue.append(node.left)
                if node.right:
                    queue.append(node.right)

            # level complete, add to depth counter
            depth += 1
        
        # overall: time complexity O(n)
        # overall: space complexity O(n)
        return depth

Aspect	Time Complexity	Space Complexity	Time Remarks	Space Remarks

543. Diameter of Binary Tree ::2:: - Easy

Topics: Tree, Depth First Search, Binary Tree

Intro

Given the root of a binary tree, return the length of the diameter of the tree. The diameter of a binary tree is the length of the longest path between any two nodes in a tree. This path may or may not pass through the root. The length of a path between two nodes is represented by the number of edges between them.

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

Constraints:

The number of nodes in the tree is in the range [0, 10⁴]

-100 ≤ Node.val ≤ 100

Abstraction

Find the diameter of a binary tree.

Space & Time Complexity

Solution	Time Complexity	Space Complexity	Time Remark	Space Remark

Bug	Error

Brute Force:

Aspect	Time Complexity	Space Complexity	Time Remarks	Space Remarks

Find the Bug:

Solution 1: DFS Post Order Recursive Global Max Diameter + (Tree Length) Pass Up - Tree/DFS Post Order Recursive Two Sided Bottom Up

    def diameterOfBinaryTree(self, root: Optional[TreeNode]) -> int:
        # Note:
        # DFS post order: left -> right -> root
        # 1. Process left -> right :
        # 2. Process -> root :  connect left and right subtrees, add edge from root -> parent
        # Result: longest path of edges

        max_diameter = 0
        
        def dfs(node):
            nonlocal max_diameter

            # Empty check
            if not node:
                return 0
            
            # Process left -> right ->
            left_len = dfs(node.left)
            right_len = dfs(node.right)
            
            # Process -> root : connect left and right subtrees
            connected_at_root = left_len + right_len

            # Update max diameters: 
            max_diameter = max(max_diameter, connected_at_root)

            # Process -> root: add edge between root -> parent
            root_len = 1 + max(left_len, right_len)

            return root_len
        
        # recursive process root
        dfs(root)

        # overall: time complexity
        # overall: space complexity
        return max_diameter

Aspect	Time Complexity	Space Complexity	Time Remarks	Space Remarks

Solution 2: DFS Post Order Recursive (Tree Max Diameter, Tree Length) Tuple Pass Up - Tree/DFS Post Order Recursive Two Sided Bottom Up

    def diameterOfBinaryTree(self, root: Optional[TreeNode]) -> int:
        # Note:
        # DFS post order: left -> right -> root
        # 1. Process left -> right :
        # 2. Process -> root : connect left and right subtrees, get root max diameter
        # Result: longest path of edges

        def dfs(node):

            # Empty check
            if not node:
                return (0, 0)
            
            # process left -> right -> :
            (left_len, left_max_diameter) = dfs(node.left)
            (right_len, right_max_diameter) = dfs(node.right)
            
            # process -> root : connect left and right subtrees
            connected_at_root = left_len + right_len
            
            # Update max diameters
            root_max_diameter = max(connected_at_root, left_max_diameter, right_max_diameter)
            
            # Process -> root: add edge between root -> parent
            root_len = 1 + max(left_len, right_len)
            
            return (root_len, root_max_diameter)
        
        # overall: time complexity
        # overall: space complexity
        return dfs(root)[1]

Aspect	Time Complexity	Space Complexity	Time Remarks	Space Remarks

Solution 3: DFS Post Order Iterative Global Max Diameter + Dictionary (Tree Length) Lookup - Tree/DFS Post Order Recursive Two Sided Bottom Up

    def diameterOfBinaryTree(self, root: Optional[TreeNode]) -> int:
        
        # Empty check
        if not root:
            return 0
        
        max_diameter = 0
        
        # iterative stack
        stack = []

        # store results 
        depth_map = defaultdict(int)
        last_visited = None
        node = root

        while stack or node:
            
            # process left -> 
            # 
            while node:
                stack.append(node)
                node = node.left
            
            # check if right subtree exists
            peek = stack[-1]

            # process -> right -> 
            # if right subtree exists and not visited yet:
            if peek.right and last_visited != peek.right:
                node = peek.right
            
            # process -> root : (after subtrees)
            else:
                # remove from stack
                stack.pop()

                # results from subtrees
                left_depth = depth_map[peek.left]
                right_depth = depth_map[peek.right]

                # process -> root : Update diameter with path through current node
                max_diameter = max(max_diameter, left_depth + right_depth)

                # process -> root : get diameter of root
                depth_map[peek] = 1 + max(left_depth, right_depth)

                # update last visited to current
                last_visited = peek

        # overall: time complexity
        # overall: space complexity
        return max_diameter

Solution 4: DFS Post Order Iterative Dictionary (Tree Max Diameter, Tree Length) Lookup - Tree/DFS Post Order Recursive Two Sided Bottom Up

    def diameterOfBinaryTree(self, root: Optional[TreeNode]) -> int:

        # Empty check
        if not root:
            return 0

        # dictionary: node -> (tree max diameter, tree length)
        node_data = defaultdict(lambda: (0, 0))

        # iterative stack
        stack = []

        curr = root
        last_visited = None

        while stack or curr:
            
            # Process left -> : 
            while curr:
                stack.append(curr)
                curr = curr.left

            # Check if right subtree exists
            peek = stack[-1]

            # Process -> right -> 
            # if right subtree exists and had not been visited:
            if peek.right and last_visited != peek.right:
                curr = peek.right

            # Process -> root
            else:
                # remove root from stack
                stack.pop()

                # grab results from subtrees
                left_edges, left_bridge = node_data[peek.left]
                right_edges, right_bridge = node_data[peek.right]

                # bridge by connecting left and right edges
                connected_bridge = left_edges + right_edges

                # max bridge between new bridge, max left bridge, and max right bridge
                root_max_bridge = max(connected_bridge, left_bridge, right_bridge)

                # length/edges at current root
                root_edges = 1 + max(left_edges, right_edges)

                # update data for current root
                node_data[peek] = (root_edges, root_max_bridge)

                # update last visited
                last_visited = peek
                
        return node_data[root][1]

110. Balanced Binary Tree ::2:: - Easy

Topics: Tree, Depth First Search, Binary Tree

Intro

Given a binary tree, determine if it is height-balanced. A height-balanced binary tree is a binary tree in which the depth of the two subtrees of every node never differs by more than one.

Example Input	Output
root = [3,9,20,null,null,15,7]	true
root = [1,2,2,3,3,null,null,4,4]	false
root = []	true

Constraints:

The number of nodes in the tree is in the range [0, 5000]

-10⁴ ≤ Node.val ≤ 10⁴

Abstraction

Determine if a binary tree is height balanced. A height-balanced binary tree is a binary tree in which the depth of the two subtrees of every node never differs by more than one.

Space & Time Complexity

Solution	Time Complexity	Space Complexity	Time Remark	Space Remark

Bug	Error

Brute Force:

Aspect	Time Complexity	Space Complexity	Time Remarks	Space Remarks

Find the Bug:

Solution 1: DFS Post Order Recursive Height or Error Pass Up - Tree/DFS Post Order Recursive Two Sided Bottom Up

    def isBalanced(self, root: Optional[TreeNode]) -> bool:
        # Note:
        # DFS post order: left -> right -> root
        # 1. Process left -> right -> :
        # 2. Process -> root : validate if balanced, throw -1 imbalance error
        # Results: detect imbalance

        def dfs(node):

            # Base case: pass height upwards
            if not node:
                return 0
            
            # process left -> right ->
            left_height = dfs(node.left)
            right_height = dfs(node.right)

            # pass thrown error upwards
            if left_height == -1 or right_height == -1:
                return -1         
            
            # process -> root : validate balanced left and right subtrees
            if abs(left_height - right_height) > 1:
                return -1
            
            root_height = 1 + max(left_height, right_height)

            # process -> root : add to height and pass to root's parent
            return root_height
        
        # overall: time complexity
        # overall: space complexity
        return dfs(root) != -1

Aspect	Time Complexity	Space Complexity	Time Remarks	Space Remarks

Solution 2: DFS Post Order Recursive Tuple (Height, Bool) Pass Up - Tree/DFS Post Order Recursive Two Sided Bottom Up

    def isBalanced(self, root: Optional[TreeNode]) -> bool:
        # Note:
        # DFS post order: left -> right -> root
        # 1. Process left -> right ->
        # 2. Process -> root : validate if balanced, pass invalid tuple error
        # Results: detect imbalance
        
        def dfs(node):

            # Base case: leaf -> (balanced:True, height:0)
            if not node:
                return (0, True)
            
            # Process left -> right -> (is_balanced, height)
            (left_height, left_bal) = dfs(node.left)
            (right_height, right_bal) = dfs(node.right)

            # pass thrown error upwards
            if not left_bal or not right_bal:
                return (-1, False)
            
            # process -> root : validate balanced left and right subtrees
            is_root_balanced = abs(left_height - right_height) <= 1

            # process -> root : add to height and pass to root's parent
            root_height = 1 + max(left_height, right_height)

            return (root_height, is_root_balanced)
        
        # overall: time complexity
        # overall space complexity
        return dfs(root)[1]

Aspect	Time Complexity	Space Complexity	Time Remarks	Space Remarks

100. Same Tree ::2:: - Easy

Topics: Tree, Depth First Search, Breadth First Search, Binary Tree

Intro

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 Input	Output
p = [1,2,3], q = [1,2,3]	true
p = [1,2], q = [1,null,2]	false
p = [1,2,1], q = [1,1,2]	false

Constraints:

The number of nodes in the tree is in the range [0, 100]

-10⁴ ≤ Node.val ≤ 10⁴

Abstraction

Determine if two different binary trees match.

Space & Time Complexity

Solution	Time Complexity	Space Complexity	Time Remark	Space Remark

Bug	Error

Brute Force: (iterative)

Aspect	Time Complexity	Space Complexity	Time Remarks	Space Remarks

Find the Bug:

Solution 1: DFS Pre Order Recursive Early Root Stop or Subtree Match Pass Up - Tree/DFS Pre Order Recursive One Sided Top Down

    def isSameTree(self, p: Optional[TreeNode], q: Optional[TreeNode]) -> bool:
        # Note:
        # DFS pre order: root -> left -> right
        # 1. Process root -> :
        #    if both nodes are 'None' -> trees match
        #    if only one node is 'None' -> trees differ
        #    if values mismatch -> trees differ
        # 3. Process -> left -> right :
        # Result: validate tree match 
        
        # Note: this is 'process root' instead of 'base case'
        # because it leads to an early termination, instead of being a regular base case
        # thus, this solution is pre order

        # Process root -> : both nodes are 'None'
        if not p and not q:
            return True

        # Process root -> : only one node is 'None' 
        if not p or not q:
            return False

        # Process root -> : values differ
        if p.val != q.val:
            return False
        
        # Process left -> right
        left_match = self.isSameTree(p.left, q.left)
        right_match = self.isSameTree(p.right, q.right)

        # Process left -> right : pass left and right results up
        subTreeMatch = left_match and right_match
        
        # overall: time complexity
        # overall: space complexity
        return subTreeMatch

Aspect	Time Complexity	Space Complexity	Time Remarks	Space Remarks

Solution 2: BFS Iterative Early Root Stop or Subtree Match Pass Up - Tree/BFS Pre Order Across Level No Explicit Level Sized Grouping Full Across Top Down

    def isSameTree(self, p: Optional[TreeNode], q: Optional[TreeNode]) -> bool:
        # Note:
        # BFS Iterate: level by level
        # 1. Process root -> : 
        #    if both nodes are 'None' -> trees match
        #    if only one node is 'None' -> trees differ
        #    if values mismatch -> trees differ
        # 2. Process -> left -> right : 
        # Result: validate tree match 
        
        # iterative stack
        queue = deque([(p, q)])
        
        while queue:

            # process root -> :
            root1, root2 = queue.popleft()
            
            # Note: early termination during process root -> : 

            # Process root -> : both nodes are 'None'
            if not root1 and not root2:
                continue
            
            # Process root -> : only one node is 'None' 
            if not root1 or not root2
                return False
            
            # Process root -> : values differ
            if root1.val != root2.val:
                return False
            
            # process -> left -> right
            queue.append((root1.left, root2.left))
            queue.append((root1.right, root2.right))
        
        # overall: time complexity
        # overall: space complexity
        return True

Aspect	Time Complexity	Space Complexity	Time Remarks	Space Remarks

572. Subtree of Another Tree ::5:: - Easy

Topics: Tree, Depth First Search, String Matching, Binary Tree, Hash Function

Intro

Given the roots of two binary trees root and subRoot, return true if there is a subtree of root with the same structure and node values of subRoot and false otherwise. A subtree of a binary tree tree is a tree that consists of a node in tree and all of this node's descendants. The tree tree could also be considered as a subtree of itself.

Example Input	Output
root = [3,4,5,1,2], subRoot = [4,1,2]	true
root = [3,4,5,1,2,null,null,null,null,0], subRoot = [4,1,2]	false

Constraints:

The number of nodes in the root tree is in the range [1, 2000].

The number of nodes in the subRoot tree is in the range [1, 1000].

-10⁴ ≤ root.val ≤ 10⁴

-10⁴ ≤ subRoot.val ≤ 10⁴

Abstraction

Determine binary tree tree2 is a subtree of binary tree tree1.

Space & Time Complexity

Solution	Time Complexity	Space Complexity	Time Remark	Space Remark

Bug	Error

Brute Force: iterative

Aspect	Time Complexity	Space Complexity	Time Remarks	Space Remarks

Find the Bug:

Solution 1: DFS Pre Order Recursive Abstraction Call Over Root Tree - Tree/DFS Pre Order Recursive One Sided Top Down

    def isSubtree(self, root: Optional[TreeNode], subRoot: Optional[TreeNode]) -> bool:
        # Note:
        # DFS pre order: root -> left -> right
        # 1. Process root -> : 
        #    validate subtree matches
        # 2. Process -> left -> right :
        # Result: validate if subtree is subtree of tree

        # helper func 
        def isSameTree(s, t):

            # process root -> : 
            if not s and not t:
                return True

            # process root -> :
            if not s or not t:
                return False

            # process root -> :
            if s.val != t.val:
                return False
            
            # process -> left -> right :
            left_match = isSameTree(s.left, t.left)
            right_match = isSameTree(s.right, t.right)

            # process -> left -> right:
            subTreeMatch = left_match and right_match

            return subTreeMatch
        

        # Empty check
        if not subRoot:
            return True

        # Empty check
        if not root:
            return False
        
        # process root -> : 
        if isSameTree(root, subRoot):
            return True
        
        # process -> left -> right :
        tree_left_subtree_match = self.isSubtree(root.left, subRoot)
        tree_right_subtree_match = self.isSubtree(root.right, subRoot) 

        # process -> left -> right :
        tree_match = tree_left_subtree_match or tree_right_subtree_match

        # overall: time complexity
        # overall: space complexity
        return tree_match

Aspect	Time Complexity	Space Complexity	Time Remarks	Space Remarks

Solution 2: BFS Pre Order Iterative Root Match Then Call isSameTree - Tree/BFS Pre Order Across Level No Explicit Level Sized Grouping Full Across Top Down

    def isSubtree(self, root: Optional[TreeNode], subRoot: Optional[TreeNode]) -> bool:
        # Note:
        # BFS order: level by level : root -> left -> right
        # 1. For each level:
        # 2. Process root -> : 
        #    if root values match, run isSameTree
        # 3. Process -> left -> right :
        # Result: validate if subtree is subtree of tree

        def isSameTree(s, t):

            # Process root -> :
            if not s and not t:
                return True

            # Process root -> : 
            if not s or not t:
                return False  

            # Process root -> : 
            if s.val != t.val:
                return False
            
            # Process -> left -> right :
            left_match = isSameTree(s.left, t.left)
            right_match = isSameTree(s.right, t.right)

            # Process -> left -> right :
            subtree_match = left_match and right_match

            return subtree_match

        # Empty check:
        if not subRoot:
            return True

        # Empty check:
        if not root:
            return False
        
        # iterative queue
        queue = deque([root])

        while queue:

            # Process root -> :
            root_node = queue.popleft()

            # Process root -> : if match, test with isSameTree
            if root_node.val == subRoot.val and isSameTree(root_node, subRoot):
                return True

            # Process -> left -> right :
            if root_node.left:
                queue.append(root_node.left)
            if root_node.right:
                queue.append(root_node.right)
        
        # overall: time complexity
        # overall: space complexity
        return False

Aspect	Time Complexity	Space Complexity	Time Remarks	Space Remarks

Solution 3: DFS Pre Order Tree Serialization Comparison - Tree/BFS Pre Order Across Level No Explicit Level Sized Grouping Full Across Top Down

    def isSubtree(self, root: Optional[TreeNode], subRoot: Optional[TreeNode]) -> bool:
        # Note:
        # DFS pre order: root -> left -> right
        # 1. Process root -> :
        #      serialize values with leading comma
        #      ("2" in "12" would match incorrectly without boundaries, so comma needed)
        #      ",2"
        # 2. Process -> left -> right :
        # Result: validate if subtree is subtree of tree

        def serialize(node):
            
            # process root -> :
            if not node:
                return ",N"

            # process root -> :
            root_serial = node.val

            # process -> left -> right :
            left_serial = serialize(node.left)
            right_serial = serialize(node.right)

            # process root -> :
            subTree_serial = f",{node.val}{left_serial}{right_serial}" 

            return subTree_serial

        # process root -> :
        serializedSubRoot = serialize(subRoot)
        serializedRoot = serialize(root)

        # process root -> :
        subTree_match = serializedSubRoot in serializedRoot

        # overall: time complexity
        # overall: space complexity
        return subTree_match

Aspect	Time Complexity	Space Complexity	Time Remarks	Space Remarks

Solution 4: DFS In Order Tree Serialization Comparison - Tree/BFS Pre Order Across Level No Explicit Level Sized Grouping Full Across Top Down

    def isSubtree(self, root: Optional[TreeNode], subRoot: Optional[TreeNode]) -> bool:
        
        def serialize(node):
            if not node:
                return ",N"

            # In-order: left -> root -> right
            left_serial = serialize(node.left)
            root_val = f",{node.val}"
            right_serial = serialize(node.right)
            
            subtree_serial = f"#{left_serial}@{root_val}${right_serial}^"
            return subtree_serial

        
        serializedSubRoot = serialize(subRoot)
        serializedRoot = serialize(root)
        
        # Check if serializedSubRoot is a substring of serializedRoot
        match = serializedSubRoot in serializedRoot

        # overall: time complexity
        # overall: space complexity
        return match

Solution 5: DFS Post Order Tree Serialization Comparison - Tree/BFS Pre Order Across Level No Explicit Level Sized Grouping Full Across Top Down

    def isSubtree(self, root: Optional[TreeNode], subRoot: Optional[TreeNode]) -> bool:
        def serialize(node):
            # Base case: null marker for missing child
            if not node:
                return ",N"
            
            # Postorder: left -> right -> root
            
            left_serial = serialize(node.left)
            right_serial = serialize(node.right)
            
            # Append root after left and right serialization
            subTree_serial = f"#{left_serial}@{right_serial},{node.val}^"            
            return subTree_serial
        
        serializedSubRoot = serialize(subRoot)
        serializedRoot = serialize(root)
        
        # Check if serializedSubRoot is a substring of serializedRoot
        match = serializedSubRoot in serializedRoot 

        # overall: time complexity
        # overall: space complexity
        return match

235. Lowest Common Ancestor of a Binary Search Tree ::2:: - Medium

Topics: Tree, Depth First Search, Binary Search Tree, Binary Tree

Intro

Given a binary search tree (BST), find the lowest common ancestor (LCA) node of two given nodes in the BST. 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 Input	Output
root = [6,2,8,0,4,7,9,null,null,3,5], p = 2, q = 8	6
root = [6,2,8,0,4,7,9,null,null,3,5], p = 2, q = 4	2
root = [2,1], p = 2, q = 1	2

Constraints:

The number of nodes in the root tree is in the range [1, 10⁵].

-10⁴ ≤ root.val ≤ 10⁴

All Node.val are unique.

p != q

p and q will exist in the BST.

Abstraction

Find lowest node that has both p and q in their subtree.

Space & Time Complexity

Solution	Time Complexity	Space Complexity	Time Remark	Space Remark

Bug	Error

Brute Force: iterative

Aspect	Time Complexity	Space Complexity	Time Remarks	Space Remarks

Find the Bug:

Solution 1: BST Recursive Traversal - Tree/BST Guided Recursive Traversal

    def lowestCommonAncestor(self, root: TreeNode, p: TreeNode, q: TreeNode) -> TreeNode:
        
        # Note:
        # BST traversal: root -> either -> left or -> right
        # 1. Process -> root : 
        #    determine if LCA is in left or right
        # 2. Process -> left or -> right :
        # Result: find LCA node
        
        # process root -> :
        # p and q are smaller, LCA in left subtree 
        if p.val < root.val and q.val < root.val:

            # process -> left :
            return self.lowestCommonAncestor(root.left, p, q)

        # process root -> :
        # p and q are larger, LCA in right subtree
        elif p.val > root.val and q.val > root.val:

            # process -> right :
            return self.lowestCommonAncestor(root.right, p, q)
        
        # process root -> :
        # p and q are in different subtrees, root is LCA
        else:
            return root

        # overall: time complexity
        # overall: space complexity

Aspect	Time Complexity	Space Complexity	Time Remarks	Space Remarks

Solution 2: BST Iterative Traversal - Tree/BST Guided Iterative Traversal

    def lowestCommonAncestor(self, root: TreeNode, p: TreeNode, q: TreeNode) -> TreeNode:
        
        # Note:
        # BST traversal: root -> either -> left or -> right
        # 1. Process -> root : 
        #    determine if LCA is in left or right
        # 2. Process -> left or -> right :
        # Result: find LCA node

        # iterative root
        while root:

            # process root -> :
            # p and q are smaller, LCA in left subtree 
            if p.val < root.val and q.val < root.val:

                # process -> left :
                root = root.left

            # process root ->
            # p and q are larger, LCA in right subtree
            elif p.val > curr.val and q.val > curr.val:

                # process -> right :
                curr = curr.right

            # process root -> :
            # p and q are in different subtrees, root is LCA
            else:
                return curr
        
        # overall: time complexity
        # overall: space complexity

Aspect	Time Complexity	Space Complexity	Time Remarks	Space Remarks

102. Binary Tree Level Order Traversal ::2:: - Medium

Topics: Tree, Breadth First Search, Binary Tree

Intro

Given the root of a binary tree, return the level order traversal of its nodes' values. (i.e., from left to right, level by level).

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

Constraints:

The number of nodes in the root tree is in the range [1, 2000].

-1000 ≤ Node.val ≤ 1000

Abstraction

Traverse a tree and return list of nodes grouped by level.

Space & Time Complexity

Solution	Time Complexity	Space Complexity	Time Remark	Space Remark

Bug	Error

Brute Force: iterative

Aspect	Time Complexity	Space Complexity	Time Remarks	Space Remarks

Find the Bug:

Solution 1: BFS Iterative - Tree/DFS Pre order Traversal

    def levelOrder(self, root: Optional[TreeNode]) -> List[List[int]]:
        
        # Empty check
        if not root:
            return []
        
        groups = []
        queue = deque([root])  # start with root
        
        while queue:
            # grab size of current level
            size = len(queue)
            level = []
            
            # process each node in this level
            for _ in range(size):
                node = queue.popleft()
                level.append(node.val)
                
                # enqueue children for next level
                if node.left:
                    queue.append(node.left)
                if node.right:
                    queue.append(node.right)
            
            groups.append(level)
        
        return groups

Aspect	Time Complexity	Space Complexity	Time Remarks	Space Remarks

Solution 2: DFS Pre Order Recursive - Tree/DFS Pre order Traversal

    def levelOrder(self, root: Optional[TreeNode]) -> List[List[int]]:
        
        # Note:
        # DFS pre order: root -> left -> right
        # 1. Process root -> :
        #    append root to corresponding depth group
        # 2. Process -> left -> right :
        # Results: nodes grouped by depth level
        
        # depth level groups
        groups = []
        
        def dfs(node, depth):

            # Empty check
            if not node:
                return
            
            # Process root -> :
            # add group if new depth reached
            if len(groups) == depth:
                groups.append([])
            
            # Process root -> : 
            # add node to corresponding depth group
            groups[depth].append(node.val)
            
            # Process -> left -> right : update depth
            dfs(node.left, depth + 1)
            dfs(node.right, depth + 1)
        
        dfs(root, 0)

        # overall: time complexity
        # overall: space complexity
        return groups

Aspect	Time Complexity	Space Complexity	Time Remarks	Space Remarks

199. Binary Tree Right Side View ::2:: - Medium

Topics: Tree, Breadth First Search, Binary Tree

Intro

Given the root of a binary tree, imagine yourself standing on the right side of it, return the values of the nodes you can see ordered from top to bottom.

Example Input	Output
root = [1,2,3,null,5,null,4]	[1,3,4]
root = [1,2,3,4,null,null,null,5]	[1,3,4,5]
root = [1,null,3]	[1,3]
root = []	[]

Constraints:

The number of nodes in the root tree is in the range [1, 100].

-100 ≤ Node.val ≤ 100

Abstraction

Given a tree, if you were to stand on the right side, return all nodes that you would have a direct line of sight to (not hidden by right-er nodes)

Space & Time Complexity

Solution	Time Complexity	Space Complexity	Time Remark	Space Remark

Bug	Error

Brute Force: iterative

Aspect	Time Complexity	Space Complexity	Time Remarks	Space Remarks

Find the Bug:

Solution 1: BFS Pre Order Iterative Grab Last Element Per Level - Tree/DFS Pre order Traversal

    def rightSideView(self, root: Optional[TreeNode]) -> List[int]:
        
        # Note:
        # BFS pre order: process level : root -> left -> right
        # 1. For each level
        # 2. Process root -> :
        #    grab length of level, if root is last element in group, add to res
        # 3. Process -> left -> right :
        # Result: right most element of each level added
        
        # Empty check
        if not root:
            return []
        
        # right most elements of each level
        result = []
        
        # iterative queue
        queue = deque([root])
        
        while queue:

            # process entire level
            level_size = len(queue)
            for i in range(level_size):

                # Process root -> : 
                node = queue.popleft()

                # Process root -> : 
                # if this is last element in level, add to res
                if i == level_size - 1:
                    result.append(node.val)

                # Process -> left -> right : 
                if node.left:
                    queue.append(node.left)
                if node.right:
                    queue.append(node.right)
        
        # overall: time complexity
        # overall: space complexity
        return result

Aspect	Time Complexity	Space Complexity	Time Remarks	Space Remarks

Solution 2: DFS Pre Order Recursive Right Subtree Search With New Depth Trigger - Tree/DFS Pre order Traversal

    def rightSideView(self, root: Optional[TreeNode]) -> List[int]:
        
        # Note:
        # DFS pre order: root -> right -> left
        # 1. Process root -> : 
        # 2. Process -> right -> left
        #    we are exploring right subtree first,
        #    first time we hit a new depth, we must be at right most node,
        #    add node to res
        # Result: right most element of each level added

        # right most elements of each level
        result = []
        
        def dfs(node, depth):

            # Empty check
            if not node:
                return

            # Process root -> :
            # if hit new depth, must be at right most node
            if depth == len(result):
                result.append(node.val)

            # Process -> right -> left
            dfs(node.right, depth + 1)
            dfs(node.left, depth + 1)
        
        # recursive call on root
        dfs(root, 0)

        # overall: time complexity
        # overall: space complexity
        return result

Aspect	Time Complexity	Space Complexity	Time Remarks	Space Remarks

1448. Count Good Nodes in Binary Tree ::2:: - Medium

Topics: Tree, Depth First Search, Breadth First Search, Binary Tree

Intro

Given a binary tree root, a node X in the tree is
named good if in the path from root to X there are no nodes with a value greater than X. Return the number of good nodes in the binary tree.

Example Input	Output
root = [3,1,4,3,null,1,5]	4
root = [3,3,null,4,2]	3
root = [1]	1

Constraints:

The number of nodes in the root tree is in the range [1, 10⁵].

Each node's value is between [-10⁴, 10⁴]

Abstraction

Given a tree, a node is good if in the path between itself and the root there is no node that is larger than it.

Space & Time Complexity

Solution	Time Complexity	Space Complexity	Time Remark	Space Remark

Bug	Error

Brute Force: iterative

Aspect	Time Complexity	Space Complexity	Time Remarks	Space Remarks

Find the Bug:

Solution 1: DFS Pre Order Recursive Pass Down Max Value Seen So Far - Tree/DFS Pre order Traversal

    def goodNodes(self, root: TreeNode) -> int:

        # Note:
        # DFS pre order: root -> left -> right
        # 1. Process root -> :
        #    check if root pass max seen so far, if so + 1 good node
        # 2. Process -> left -> right :
        # Result: good nodes counted

        def dfs(node, max_so_far):

            # Empty check
            if not node:
                return 0
            
            # Process root -> : 
            # if root >= max_so_far, + 1 good
            good = 1 if node.val >= max_so_far else 0
            
            # Process root -> : update max
            new_max = max(max_so_far, node.val)
            
            # Process -> left -> right :
            good += dfs(node.left, new_max)
            good += dfs(node.right, new_max)
            
            # Process root -> : pass good nodes
            return good
        
        good_nodes = dfs(root, root.val)

        # overall: time complexity
        # overall: space complexity
        return good_nodes

Aspect	Time Complexity	Space Complexity	Time Remarks	Space Remarks

Solution 2: DFS Pre Order Iterative Pass (Root, Max_So_Far) Tuple Down - Tree/DFS Pre order Traversal

    def goodNodes(self, root: TreeNode) -> int:
        
        # Note:
        # DFS pre order: root -> left -> right
        # 1. Process root -> :
        #    check if root pass max seen so far, if so + 1 good node
        # 2. Process -> left -> right :
        # Result: good nodes counted

        # global good count
        count = 0

        # iterative stack
        queue = deque([(root, root.val)])
        
        while queue:

            # Process root -> : 
            (root, max_so_far) = queue.popleft()
            
            # Process root -> : check if good node
            if root.val >= max_so_far:
                count += 1
            
            # Process root -> : update max
            new_max = max(max_so_far, root.val)
            
            # Process -> left -> right :
            if root.left:
                queue.append((root.left, new_max))
            if root.right:
                queue.append((root.right, new_max))
        
        # overall: time complexity
        # overall: space complexity
        return count

Aspect	Time Complexity	Space Complexity	Time Remarks	Space Remarks

98. Validate Binary Search Tree ::2:: - Medium

Topics: Tree, Depth First Search, Binary Search Tree, Binary Tree

Intro

Given the root of a binary tree, determine if it is a valid binary search tree (BST). The left subtree of a node contains only nodes with keys strictly less than the node's key. The right subtree of a node contains only nodes with keys strictly greater than the node's key. Both the left and right subtrees must also be binary search trees.

Example Input	Output
root = [2,1,3]	true
root = [5,1,4,null,null,3,6]	false

Constraints:

The number of nodes in the root tree is in the range [1, 10⁴].

-2³¹ ≤ Node.val ≤ 2³¹-1

Abstraction

Given a tree, determine if tree is a valid BST. Where value of nodes is always: left.val ≤ root.val ≤ right.val

Space & Time Complexity

Solution	Time Complexity	Space Complexity	Time Remark	Space Remark

Bug	Error

Brute Force: iterative

Aspect	Time Complexity	Space Complexity	Time Remarks	Space Remarks

Find the Bug:

Solution 1: DFS Pre Order Recursive Passing Range Limits - Tree/DFS Pre order Traversal

    def isValidBST(self, root: Optional[TreeNode]) -> bool:
        
        # Note:
        # DFS pre order: root -> left -> right
        # 1. Process root -> :
        #    validate order
        # 2. Process -> left -> right : 
        # Result: validated BST
        
        def dfs(node, low, high):

            # Process root -> : 
            if not node:
                return True

            # Process root -> : validate order
            if not (low < node.val < high):
                return False

            # Process -> left -> right :
            left_valid = dfs(node.left, low, node.val)
            right_valid = dfs(node.right, node.val, high)

            # Process -> left -> right :
            subtreeValid = left_valid and right_valid

            return subtreeValid

        # Start with infinite bounds
        treeValid = dfs(root, float('-inf'), float('inf'))

        # overall: time complexity
        # overall: space complexity
        return treeValid

Aspect	Time Complexity	Space Complexity	Time Remarks	Space Remarks

Solution 2: BFS Pre Order Iterative Passing Queuing Range Limits - Tree/DFS Pre order Traversal

    def isValidBST(self, root: Optional[TreeNode]) -> bool:

        # Note:
        # BFS pre order: process level: root -> left -> right
        # 1. Process level: 
        #      Process root -> :
        #        validate range limits
        # 2. Process -> left -> right : 
        # Result: validated BST

        # iterative queue
        queue = deque([(root, float('-inf'), float('inf'))])

        while queue:

            # Process root -> :
            node, low, high = queue.popleft()

            # Process root -> : 
            if not node:
                continue

            # Process root -> : validate order
            if not (low < node.val < high):
                return False

            # Process -> left -> right :
            queue.append((node.left, low, node.val))
            queue.append((node.right, node.val, high))

        # overall: time complexity
        # overall: space complexity
        return True

230. Kth Smallest Element in a BST ::2:: - Medium

Topics: Tree, Depth First Search, Binary Search Tree, Binary Tree

Intro

Given the root of a binary search tree, and an integer k, return the kth smallest value (1-indexed) of all the values of the nodes in the tree. Follow up: If the BST is modified often (i.e., we can do insert and delete operations) and you need to find the kth smallest frequently, how would you optimize?

Example Input	Output
root = [3,1,4,null,2], k = 1	1
root = [5,3,6,2,4,null,null,1], k = 3	3

Constraints:

The number of nodes in the root tree is n

1 ≤ k ≤ n ≤ 10⁴

0 ≤ Node.val ≤ 10⁴

Abstraction

Given a BST, find the kth smallest node.

Space & Time Complexity

Solution	Time Complexity	Space Complexity	Time Remark	Space Remark

Bug	Error

Brute Force: iterative

Aspect	Time Complexity	Space Complexity	Time Remarks	Space Remarks

Find the Bug:

Solution 1: DFS In Order Recursive Early Stop with Global Element Counter - Tree/DFS Pre order Traversal

    def isValidBST(self, root: Optional[TreeNode]) -> bool:

        # Note:
        # DFS in order: left -> root -> right
        # 1. Process left -> : 
        # 2. Process -> root -> :
        #    if reached kth node, return
        # 3. Process -> right :
        # Result: kth smallest found

        # global counter
        k = k
        # global pointer
        result = None
        
        def inorder(node):
            nonlocal k
            nonlocal result

            # Process left -> :
            if not node or result is not None:
                return
            
            # Process left -> :
            inorder(node.left)
            
            # Process root -> : 
            # if kth node, return
            k -= 1
            if k == 0:
                result = node.val
                return
            
            # Process right -> : 
            inorder(node.right)
        
        inorder(root)

        # overall: time complexity
        # overall: space complexity
        return result

Aspect	Time Complexity	Space Complexity	Time Remarks	Space Remarks

Solution 2: DFS In Order Iterative with Element Counter - Tree/DFS Pre order Traversal

    def isValidBST(self, root: Optional[TreeNode]) -> bool:

        # Note:
        # DFS in order: left -> root -> right
        # 1. Process left -> : 
        # 2. Process -> root -> :
        #    if reached kth node, return
        # 3. Process -> right :
        # Result: kth smallest found

        # iterative stack
        stack = []
        
        while True:

            # Process left -> :
            while root:
                stack.append(root)
                root = root.left
            
            # Process -> root -> :
            root = stack.pop()

            # Process -> root -> : 
            # if kth node, return
            k -= 1
            if k == 0:
                return root.val
            
            # Process -> right :
            root = root.right

        # overall: time complexity
        # overall: space complexity

Aspect	Time Complexity	Space Complexity	Time Remarks	Space Remarks

105. Construct Binary Tree from Pre Order and In Order Traversal ::2:: - Medium

Topics: Array, Hash Table, Divide and Conquer, Tree, Binary Tree

Intro

Given two integer arrays pre order and in order where pre order is the pre order traversal of a binary tree and inorder is the inorder traversal of the same tree, construct and return the binary tree.

Example Input	Output
preorder = [3,9,20,15,7], inorder = [9,3,15,20,7]	[3,9,20,null,null,15,7]
preorder = [-1], inorder = [-1]	[-1]

Constraints:

1 ≤ preorder.length ≤ 3000

inorder.length == preorder.length

-3000 ≤ preorder[i], inorder[i] ≤ 3000

Each value or inorder also appears in preorder.

preorder is guaranteed to be the preorder traversal of the tree.

inorder is guaranteed to be the inorder traversal of the tree.

Abstraction

Create original free given pre and post order traversals.

Space & Time Complexity

Solution	Time Complexity	Space Complexity	Time Remark	Space Remark

Bug	Error

Brute Force: iterative

Aspect	Time Complexity	Space Complexity	Time Remarks	Space Remarks

Find the Bug:

Solution 1: DFS Pre Order Recursive In Order Hash Map - Tree/DFS Pre order Traversal

    def buildTree(self, preorder: List[int], inorder: List[int]) -> Optional[TreeNode]:

        # Tree:
        #        1
        #       / \
        #      2   3
        #     / \   \
        #    4   5   6
        #             \
        #              7
    
        # Pre order: root -> left -> right
        # [1, 2, 4, 5, 3, 6, 7]

        # In order: left -> root -> right 
        # [4, 2, 5, 1, 3, 6, 7]

        # Note:
        # Pre order: current root supplier
        # by iterating over this: root -> left -> right

        # In order: recursive range provider
        # due to Invariant from: left -> root -> right
        # for all roots -> [ leftSubtree, root, rightSubtree ]

        # val -> in order array index
        inorder_index_map = {val: idx for idx, val in enumerate(inorder)}

        # iterating over pre order: the current root supplier, 
        # will determine which tree we are currently building
        pre_idx = 0


        # recurse over in order list 
        def array_to_tree(left, right):
            nonlocal pre_idx

            # Base case: no elements to construct subtree
            if left > right:
                return None

            # 1. curr 'root': root -> left -> right
            root_val = preorder[pre_idx]
            
            # prepare next root ('left'): above becomes -> left -> right
            pre_idx += 1

            # Create root node
            root = TreeNode(root_val)

            # 2: Find root's index for in order 
            #    to trigger invariant [leftSubtree, root, rightSubtree]
            root_index = inorder_index_map[root_val]

            # 3: given invariant, 
            #    trigger left subtree range for in order array
            left_subtree_left = left
            left_subtree_right = root_index - 1

            # 4: given invariant, 
            #    trigger right subtree range for in order array
            right_subtree_left = root_index + 1
            right_subtree_right = right

            # 5: pass left subtree range
            root.left = array_to_tree(left_subtree_left, left_subtree_right)

            # 5: pass] right subtree range
            root.right = array_to_tree(right_subtree_left, right_subtree_right)

            # root with subtrees
            return root

        # initialize bounds for topmost root
        left_start = 0 
        right_start = len(inorder)-1

        # recurse starting at topmost root, 
        # rest of tree created by recursion (magic)
        orig_tree = array_to_tree(left_start, right_start)

        # overall: time complexity
        # overall: space complexity 
        return array_to_tree(left_start, right_start)

Aspect	Time Complexity	Space Complexity	Time Remarks	Space Remarks

Solution 2: DFS Pre Order Iterative Build Using Stack - Tree/DFS Pre order Traversal

    def buildTree(self, preorder: List[int], inorder: List[int]) -> Optional[TreeNode]:

        # Tree:
        #        1
        #       / \
        #      2   3
        #     / \   \
        #    4   5   6
        #             \
        #              7
    
        # Pre order: root -> left -> right
        # [1, 2, 4, 5, 3, 6, 7]

        # In order: left -> root -> right 
        # [4, 2, 5, 1, 3, 6, 7]

        # Empty check
        if not preorder or not inorder:
            return None
        
        # 1: topmost root -> preorder[0]
        #.   iterate over preorder, create and connect with parent
        root = TreeNode(preorder[0])

        # 2: stack: 
        #    filled by iterative preorder root -> left -> right
        #    holds roots that are waiting for subtrees
        stack = [root]

        # 2: inorder_index:
        #  start at bottom left most subtree 0
        inorder_index = 0

        # In order invariant -> [leftSubtree, root, rightSubtree]
        # when inorder index pointing to some root:
        #   1) root has no left subtrees
        #   2) root's left subtrees have been created and assigned

        # 3: iterate over preorder: root -> left -> right
        for i in range(1, len(preorder)):

            # peek top of stack:
            # previous node waiting for subtrees
            top = stack[-1]

            # pre order: subtree of top
            preorder_val = preorder[i]
            
            # in order: left most complete root
            inorder_val = inorder[inorder_index]

            # if top of stack is not complete
            # preorder is the tops left subtree
            if top.val != inorder_val:

                # connect and push to stack,
                # to find left subtrees subtrees
                top.left = TreeNode(preorder_val)
                stack.append(top.left)
                        
            # if top of stack is complete
            # preorder is the tops right subtree
            else:
                
                # now we have arrive to top most root,
                # if in order marks as complete, that means there ar
                while stack and stack[-1].val == inorder[inorder_index]:
                    top = stack.pop()
                    inorder_index += 1
                
                # process -> right :
                # preorder_val is a right child, connect and push to stack
                top.right = TreeNode(preorder_val)
                stack.append(top.right)
        
        # overall: time complexity
        # overall: space complexity
        return root

Aspect	Time Complexity	Space Complexity	Time Remarks	Space Remarks

124. Binary Tree Maximum Path Sum ::1:: - Hard

Topics: Dynamic Programming, Tree, Depth First Search, Binary Tree

Intro

A path in a binary tree is a sequence of nodes where each pair of adjacent nodes in the sequence has an edge connecting them. A node can only appear in the sequence at most once. Note that the path does not need to pass through the root. The path sum of a path is the sum of the node's values in the path. Given the root of a binary tree, return the maximum path sum of any non-empty path.

Example Input	Output
root = [1,2,3]	6
root = [-10,9,20,null,null,15,7]	42

Constraints:

The number of nodes in the tree is in the range [1, 3 * 10⁴]

-1000 ≤ Node.val ≤ 1000

Abstraction

Given a tree, find the path that produces the max sum.

Space & Time Complexity

Solution	Time Complexity	Space Complexity	Time Remark	Space Remark

Bug	Error

Brute Force: iterative

Aspect	Time Complexity	Space Complexity	Time Remarks	Space Remarks

Find the Bug:

Solution 1: DFS Post Order Recursive Global Max Tracker - Tree/DFS Pre order Traversal

    def maxPathSum(self, root: Optional[TreeNode]) -> int:
        
        # Note:
        # DFS post order: left -> right -> root
        # 1. Process left -> right -> :
        # 2. Process -> root :
        #     

        # global max
        max_sum = float('-inf')

        def dfs(node):
            nonlocal max_sum

            # Empty check
            if not node:
                return 0

            # Process left -> right -> 
            left_gain = max(dfs(node.left), 0)
            right_gain = max(dfs(node.right), 0)

            # Process -> root :
            connected_at_root = node.val + left_gain + right_gain

            # Process -> root : check global max
            max_sum = max(max_sum, connected_at_root)

            # Process -> root : get max path at root
            root_max_path = node.val + max(left_gain, right_gain)

            return root_max_path

        dfs(root)

        # overall: time complexity
        # overall: space complexity
        return max_sum

Aspect	Time Complexity	Space Complexity	Time Remarks	Space Remarks

297. Serialize and Deserialize Binary Tree ::2:: - Hard

Topics: String, Tree, Depth First Search, Breadth First Search, Design, Binary Tree

Intro

Serialization is the process of converting a data structure or object into a sequence of bits so that it can be stored in a file or memory buffer, or transmitted across a network connection link to be reconstructed later in the same or another computer environment. Design an algorithm to serialize and deserialize a binary tree. There is no restriction on how your serialization/deserialization algorithm should work. You just need to ensure that a binary tree can be serialized to a string and this string can be deserialized to the original tree structure. Clarification: The input/output format is the same as how LeetCode serializes a binary tree. ou do not necessarily need to follow this format, so please be creative and come up with different approaches yourself.

Example Input	Output
root = [1,2,3,null,null,4,5]	[1,2,3,null,null,4,5]
root = []	[]

Constraints:

The number of nodes in the tree is in the range [1, 10⁴]

-1000 ≤ Node.val ≤ 1000

Abstraction

Create a serialize and deserialize functions for trees

Space & Time Complexity

Solution	Time Complexity	Space Complexity	Time Remark	Space Remark

Bug	Error

Brute Force: iterative

Aspect	Time Complexity	Space Complexity	Time Remarks	Space Remarks

Find the Bug:

Solution 1: DFS Pre Order Recursive - Tree/DFS Pre order Traversal

class Codec:

    def serialize(self, root):

        # Note: 
        # DFS pre order: root -> left -> right:
        # 1. Process root -> :
        #    if val, append val 
        #    if None, append marker
        # 2. Process -> left -> right :
        # Result: serialized pre order tree 

        vals = []

        def dfs(node):

            # Process root -> :
            if not node:
                vals.append("N")
                return

            # Process root -> :
            vals.append(str(node.val))

            # Process -> left -> right :
            dfs(node.left)
            dfs(node.right)

        dfs(root)

        # overall: time complexity
        # overall: time complexity
        return ",".join(vals)
        

    def deserialize(self, data):
        
        # Note:
        # DFS pre order: root -> left -> right :
        # 1. Process root :
        #.   if val

        # deserialize string into queue
        vals = deque(data.split(","))

        def dfs():
            
            # Process root -> :
            if not vals:
                return None

            # Process root -> :
            val = vals.popleft()
            if val == "N":
                return None

            # Process root -> :
            node = TreeNode(int(val))

            # Process -> left -> right :
            node.left = dfs()
            node.right = dfs()

            return node

        # new root of tree
        return dfs()

Aspect	Time Complexity	Space Complexity	Time Remarks	Space Remarks