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] Recursive DFS Post Order Pass Up Inverted Subtrees - Tree/DFS Post Order Recursive Two Sided Bottom Up

    def invertTree(self, root: Optional[TreeNode]) -> Optional[TreeNode]:
        
        # Tree:
        # A tree is made up of nodes which point to other nodes
        # They must have pointers and they may or may not have values:
        #      ()             1
        #      / \           / \
        #    ()   ()        2   3 
        #         / \           / \
        #       ()   ()        4   5

        # To invert a tree, we simply have to swap 
        # the L and R children nodes at each node:
        #       1
        #      / \
        #     3   2
        #    / \
        #   4   5

        # DFS PostOrder: 
        # left -> right -> root
        #   1. Process left node: invert children nodes
        #   2. Process right node: invert children nodes
        #   3. Process root node: invert left and right nodes

        # Base case: reached leaf of tree, no swap, return None
        if not root:
            return None

        # Recursive call to process left subtrees
        left_inverted = self.invertTree(root.left)

        # Recursive call to process right subtrees
        right_inverted = self.invertTree(root.right)

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

        # Process Root: 
        # Invert left and right nodes
        root.left = right_inverted
        root.right = left_inverted

        # Return invert to previous recursive call

        # overall: tc O(n)
        # overall: sc O(h), O(log n) for balanced tree
        return root

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

    def invertTree(self, root: Optional[TreeNode]) -> Optional[TreeNode]:
        
        # Tree:
        # A tree is made up of nodes which point to other nodes
        # They must have pointers and they may or may not have values:
        #      ()             1
        #      / \           / \
        #    ()   ()        2   3 
        #         / \           / \
        #       ()   ()        4   5

        # To invert a tree, we simply have to swap 
        # the L and R children nodes at each node:
        #       1
        #      / \
        #     3   2
        #    / \
        #   4   5

        # DFS PostOrder: 
        # left -> right -> root
        #   1. Process left node: invert children nodes
        #   2. Process right node: invert children nodes
        #   3. Process root node: invert left and right nodes

        # Empty Case: tree is a leaf, no swap, return None
        if not root:
            return None

        # Stack to hold:
        stack = []

        # Starting Iteration:
        curr = root

        # Tracking Last Visited:
        lastVisited = None 

        # Check: if we still have nodes to process
        # tc: iterate over n O(n)
        while stack or curr:

            # Process Left Node: 
            # iterate as far down the left subtree line as we can,
            # by as many left subtree nodes to stack as we can
            while curr: 
                # push root node to stack
                stack.append(curr)
                # iterate to left node
                curr = curr.left

            # Implies: reached the last node on the left subtree line

            # Grab: root node we just placed on stack (root of last left subtree)
            peek = stack[-1]

            # Check: if root node of the last left subtree has a right subtree
            # Check: if right subtree has not been visited
            # Then: iterate to right subtree and in next while loop, 
            #       the left subtree of the right subtree will be explored fully
            if peek.right and lastVisited != peek.right:
                curr = peek.right
            
            # Implies: no right subtree exists
            # Implies: finished processing left and right subtree
            # Then: process root 
            else:
                # Remove And Process: pop root node from stack
                stack.pop()

                # Process Root Node:
                # Invert left and right nodes
                peek.left, peek.right = peek.right, peek.left

                # Mark Root Node:
                # Set last visited to current to avoid revisiting
                lastVisited = peek

        # tc: 
        # sc:
        return root

Solution 3: [BFS] Iterative BFS Pre Order 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]:
        
        # Tree:
        # A tree is made up of nodes which point to other nodes
        # They must have pointers and they may or may not have values:
        #      ()             1
        #      / \           / \
        #    ()   ()        2   3 
        #         / \           / \
        #       ()   ()        4   5

        # To invert a tree, we simply have to swap 
        # the L and R children nodes at each node:
        #       1
        #      / \
        #     3   2
        #    / \
        #   4   5

        # BFS Iterative Level By Level: 
        # Process root level -> process left and right level
        #   1. Process Root: iterate over roots level
        #        - swap left and right subtrees
        #   2. Process Left And Right: append left and right nodes to process them
        #        - left and right will be process along with all nodes in their level
        
        # Empty Case: tree is a leaf, no swap, return None
        if not root:
            return None
        
        # Iterative level stack:
        queue = deque([root])
        
        # Check: if we still have nodes to process
        # tc: iterate over n O(n)
        while queue:

            # Number Of Nodes In Current Level Of Tree:
            size = len(queue)

            # Process The full Level Before Iterating To Next Level:
            for _ in range(size):

                # Remove And Process:
                # Pop root node from left most of stack,
                # processing each level from left to right
                node = queue.popleft()
                
                # Process Root Node:
                # Invert left and right nodes
                node.left, node.right = node.right, node.left
                
                # Prepare Next Level:
                # Append the next level of nodes to the stack,
                # will not affect the current level processing 
                # as we have previously determined the number of nodes in the level 
                # and thus the number of nodes to be process
                if node.left:
                    queue.append(node.left)
                if node.right:
                    queue.append(node.right)
        
        # overall: tc O(n)
        # overall: sc O(n)
        return root

Aspect	Time Complexity	Space Complexity	Time Remarks	Space Remarks

104. Maximum Depth of Binary Tree ::3:: - 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] Recursive DFS Post Order Pass Up Subtree Depth - Tree/DFS Post Order Recursive Two Sided Bottom Up

    def maxDepth(self, root: Optional[TreeNode]) -> int:
                
        # Tree:
        # A tree is made up of nodes which point to other nodes
        # They must have pointers and they may or may not have values:
        #      ()             1
        #      / \           / \
        #    ()   ()        2   3 
        #         / \           / \
        #       ()   ()        4   5

        # To find the height of a tree, we simply have to compare
        # the max height of each subtree at each root node, 
        # and keep track of the max height found, while adding +1
        # to account for the current root node

        # DFS PostOrder: 
        # left -> right -> root
        #   1. Process left node: get height of tree
        #   2. Process right node: get height of tree
        #   3. Process root node: compare max height between left and right, add +1
        
        # Empty Case: tree is a leaf, no height, return 0
        if not root:
            return 0
        
        # Recursive call to process left subtrees
        left_depth = self.maxDepth(root.left)

        # Recursive call to process right subtrees
        right_depth = self.maxDepth(root.right)
        
        # Could have also been: right -> left subtrees
        # right_depth = self.maxDepth(root.right)
        # left_depth = self.maxDepth(root.left)

        # Process Root:
        # compare max height between left and right, add 1
        root_depth = 1 + max(left_depth, right_depth)

        # Return max height of tree

        # overall: tc O(n)
        # overall: sc O(n)
        return root_depth

Aspect	Time Complexity	Space Complexity	Time Remarks	Space Remarks

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

    def maxDepth(self, root: Optional[TreeNode]) -> int:
        
        # Tree:
        # A tree is made up of nodes which point to other nodes
        # They must have pointers and they may or may not have values:
        #      ()             1
        #      / \           / \
        #    ()   ()        2   3 
        #         / \           / \
        #       ()   ()        4   5

        # To find the height of a tree, we simply have to swap compare
        # the max height of each subtree at each root node, 
        # and keep track of the max height found
        
        # DFS PostOrder: 
        # left -> right -> root
        #   1. Process left node: get height of tree
        #   2. Process right node: get height of tree
        #   3. Process root node: compare max height between left and right
        
        # Empty Case: tree is a leaf, no height, return = 0
        if not root:
            return 0

        # Stack to hold:
        stack = []

        # Starting Iteration:
        curr = root

        # Tracking Last Visited:
        lastVisited = None

        # Iterative Height Map Tracking:
        # Since we are using a stack, we will not have access to
        # the children left and right at the same time, so we need to
        # keep track of the heights in the hashmap
        heightMap = defaultdict(int)

        # Check: of we still have nodes to process
        # tc: iterate over n O(n)
        while stack or curr:
            
            # Process Left Node: 
            # iterate as far down the left subtree line as we can,
            # by as many left subtree nodes to stack as we can
            while curr:
                # push root node to stack
                stack.append(curr)
                # iterate to left node
                curr = curr.left
            
            # Implies: reached the last node on the left subtree line

            # Grab: root node we just placed on stack (root of last left subtree)
            peek = stack[-1]

            # Check: if root node of the last left subtree has a right subtree
            # Check: if right subtree has not been visited
            # Then: iterate to right subtree and in next while loop, 
            #       the left subtree of the right subtree will be explored fully
            if peek.right and lastVisited != peek.right:
                curr = peek.right

            # Implies: no right subtree exists
            # Implies: finished processing left and right subtree
            # Then: process root 
            else:
                # Remove And Process: pop root node from stack
                stack.pop()
                
                # Grab left and right height result from hashmap 
                left_depth = heightMap[peek.left]
                right_depth = heightMap[peek.right]

                # Process Root Node:
                # compare max height between left and right, add 1
                currentDepth = 1 + max(left_depth, right_depth)

                # Track Root Node:
                # Add this nodes height to the dictionary
                heightMap[peek] = currentDepth

                # Mark Root Node:
                # Set last visited to current to avoid revisiting
                lastVisited = peek

        # final height of tree
        heightOfTree = heightMap[root]

        # overall: tc 
        # overall: sc 
        return heightOfTree

Solution 3: [BFS] Iterative BFS Pre Order 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:
       
        # Tree:
        # A tree is made up of nodes which point to other nodes
        # They must have pointers and they may or may not have values:
        #      ()             1
        #      / \           / \
        #    ()   ()        2   3 
        #         / \           / \
        #       ()   ()        4   5

        # To find the height of a tree, we simply have to swap compare
        # the max height of each subtree at each root node, 
        # and keep track of the max height found

        # BFS Iterative Level By Level: 
        # Process root level -> process left and right level
        #   1. Process Root: iterate over roots level 
        #       - no action needed, when finished iteration over nodes in 
        #         level, added 1 to global depth counter
        #   2. Process Left And Right: append left and right nodes to process them
        #        - left and right will be process along with all nodes in their level
        
        # Empty Case: tree is a leaf, no height, return = 0
        if not root:
            return 0
        
        # Iterative level stack:
        stack = [(root, 1)]

        # Global depth
        globalDepth = 0
        
        # Check: if we still have nodes to process
        # tc: iterate over n O(n)
        while queue:

            # Number Of Nodes In Current Level Of Tree:
            size = len(queue)

            # Process The full Level Before Iterating To Next Level:
            for _ in range(size):

                # Remove And Process:
                # no action needed on root node
                node = queue.popleft()

                # Prepare Next Level:
                # Append the next level of nodes to the stack,
                # will not affect the current level processing 
                # as we have previously determined the number of nodes in the level 
                # and thus the number of nodes to be process
                if node.left:
                    queue.append(node.left)
                if node.right:
                    queue.append(node.right)

            # level complete, add +1 to depth counter to account for this level
            globalDepth += 1
        
        # overall: tc O(n)
        # overall: sc O(n)
        return globalDepth

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 DFS 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 BFS 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

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

987. Vertical Order Traversal of a Binary Tree ::1:: - Hard

Topics: Hash Table, Tree, Depth First Search, Breath First Search, Sorting, Binary Tree

Intro

Given the root of a binary tree, calculate the vertical order traversal of the binary tree. For each node at position (row, col), its left and right children will be at positions (row + 1, col - 1) and (row + 1, col + 1) respectively. The root of the tree is at (0, 0) The vertical order traversal of a binary tree is a list of top-to-bottom orderings for each column index starting from the leftmost column and ending on the rightmost column. There may be multiple nodes in the same row and same column. In such a case, sort these nodes by their values. Return the vertical order traversal of the binary tree.

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

Constraints:

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

0 ≤ Node.val ≤ 1000

Abstraction

something!

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] Re Rooting DP On Trees - Tree/DFS Post Order Recursive Two Sided Bottom Up

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

        # DFS + Coordinate Tracking + Sorting
        
        # Idea:
        #   - Each node has coordinates (row, col)
        #   - Left child  -> (row + 1, col - 1)
        #   - Right child -> (row + 1, col + 1)
        #   - Store all nodes as (col, row, value)
        #   - Sort to satisfy vertical traversal ordering.
        
        # Rules:
        #   1. DFS traversal assigning coordinates.
        #   2. Sort by column, row, value.
        #   3. Group nodes by column.
        
        # Complexity:
        #   - Time: O(n log n)   (sorting)
        #   - Space: O(n)

        nodes = []  # (col, row, value)

        # DFS traversal
        def dfs(node, row, col):
            if not node:
                return

            nodes.append((col, row, node.val))

            dfs(node.left, row + 1, col - 1)
            dfs(node.right, row + 1, col + 1)

        dfs(root, 0, 0)

        # Sort by col -> row -> value
        nodes.sort()

        # Group by column
        res = []
        prev_col = float('-inf')

        for col, row, val in nodes:
            if col != prev_col:
                res.append([])
                prev_col = col
            res[-1].append(val)

        return res

Solution 2: [BFS] something bfs - Tree/BFS Pre Order Across Level For Level Size Based Grouping Full Across Top Down

    def verticalTraversal(self, root: Optional[TreeNode]) -> List[List[int]]:
        # BFS: enqueue (node, row, col)
        # Collect all (col, row, val) tuples, then sort + group

        nodes = []  # (col, row, val)
        queue = deque([(root, 0, 0)])

        while queue:
            node, row, col = queue.popleft()

            nodes.append((col, row, node.val))

            if node.left:
                queue.append((node.left, row + 1, col - 1))
            if node.right:
                queue.append((node.right, row + 1, col + 1))

        # Sort by col -> row -> val
        nodes.sort()

        # Group by column
        res = []
        prev_col = float('-inf')

        for col, row, val in nodes:
            if col != prev_col:
                res.append([])
                prev_col = col
            res[-1].append(val)

        return res

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

LeetCode: Trees II DFS BFS