Advanced Trees (Hard)Master complex tree algorithms: Traversals, BST operations, and advanced structural problems.

244. Level Order Traversal

Problem Statement

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:** ```python Input: root = [3,9,20,null,null,15,7] Output: [[3],[9,20],[15,7]] ```

Approach

1. **BFS Approach**: Level order traversal is essentially Breadth-First Search (BFS). 2. **Queue**: Use a queue to keep track of nodes. 3. **Level Tracking**: * Iterate while the queue is not empty. * Get the current size of the queue (number of nodes in the current level). * Iterate through that number of nodes, processing them and adding their children to the queue. * Store the values of the current level in a list. 4. **Result**: Append each level's list to the final result.

Solution

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

def levelOrder(root):
    if not root:
        return []
    
    result = []
    queue = [root]
    
    while queue:
        level_size = len(queue)
        current_level = []
        
        for _ in range(level_size):
            node = queue.pop(0)
            current_level.append(node.val)
            
            if node.left:
                queue.append(node.left)
            if node.right:
                queue.append(node.right)
                
        result.append(current_level)
        
    return result

245. Maximum Depth of Binary Tree

Problem Statement

Given the `root` of a binary tree, return its maximum depth. A binary tree's maximum depth is the number of nodes along the longest path from the root node down to the farthest leaf node. **Example:** ```python Input: root = [3,9,20,null,null,15,7] Output: 3 ```

Approach

1. **Recursive Approach**: * Base case: If `root` is `None`, depth is 0. * Recursive step: Depth is `1 + max(depth(left), depth(right))`. 2. **Iterative Approach (BFS)**: * Use level order traversal. * Increment depth counter for each level processed.

Solution

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

def maxDepth(root):
    if not root:
        return 0
        
    left_depth = maxDepth(root.left)
    right_depth = maxDepth(root.right)
    
    return 1 + max(left_depth, right_depth)

246. Diameter of Binary Tree

Problem Statement

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:** ```python Input: root = [1,2,3,4,5] Output: 3 Explanation: 3 is the length of the path [4,2,1,3] or [5,2,1,3]. ```

Approach

1. **Definition**: The longest path through a node is `depth(left_child) + depth(right_child)`. 2. **Global Max**: We want to find this value for *every* node and take the maximum. 3. **DFS with Side Effect**: * Modify the `maxDepth` function. * At each node, calculate `left_depth` and `right_depth`. * Update a global `max_diameter` variable with `left_depth + right_depth`. * Return `1 + max(left_depth, right_depth)` to the parent so calculation continues up.

Solution

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

class Solution:
    def diameterOfBinaryTree(self, root):
        self.max_diameter = 0
        
        def depth(node):
            if not node: return 0
            
            left = depth(node.left)
            right = depth(node.right)
            
            # The path through this node is left + right
            self.max_diameter = max(self.max_diameter, left + right)
            
            # Return height for parent
            return 1 + max(left, right)
            
        depth(root)
        return self.max_diameter

249. Validate Binary Search Tree

Problem Statement

Given the `root` of a binary tree, determine if it is a valid binary search tree (BST). A valid BST is defined as follows: * The left subtree of a node contains only nodes with keys **less than** the node's key. * The right subtree of a node contains only nodes with keys **greater than** the node's key. * Both the left and right subtrees must also be binary search trees. **Example:** ```python Input: root = [2,1,3] Output: true ```

Approach

1. **Range Check**: Each node must be within a valid range `(min, max)`. 2. **Recursive Logic**: * Root is valid if `-inf < root.val < inf`. * Left child must be in range `(min, root.val)`. * Right child must be in range `(root.val, max)`. 3. **Traversal**: Start with `validate(root, -inf, inf)` and traverse down.

Solution

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

def isValidBST(root):
    def validate(node, low, high):
        if not node:
            return True
            
        if not (low < node.val < high):
            return False
            
        return (validate(node.left, low, node.val) and
                validate(node.right, node.val, high))
                
    return validate(root, float('-inf'), float('inf'))

251. Serialize and Deserialize Binary Tree

Problem Statement

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. Design an algorithm to serialize and deserialize a binary tree. There is no restriction on how your serialization/deserialization algorithm should work. **Example:** ```python Input: root = [1,2,3,null,null,4,5] Output: [1,2,3,null,null,4,5] ```

Approach

1. **Preorder Traversal (DFS)**: This is usually easiest. 2. **Serialize**: * If node is `None`, append a special marker (e.g., "#"). * Otherwise, append `str(val)`. * Recurse left, then right. * Join with commas. 3. **Deserialize**: * Split the string into a list of values. * Use an iterator or pointer. * If value is "#", return `None`. * Create node with value. * Recursively build `node.left` and `node.right`.

Solution

class Codec:
    def serialize(self, root):
        vals = []
        def encode(node):
            if not node:
                vals.append('#')
                return
            vals.append(str(node.val))
            encode(node.left)
            encode(node.right)
        encode(root)
        return ' '.join(vals)

    def deserialize(self, data):
        vals = iter(data.split())
        def decode():
            val = next(vals)
            if val == '#':
                return None
            node = TreeNode(int(val))
            node.left = decode()
            node.right = decode()
            return node
        return decode()

# Your Codec object will be instantiated and called as such:
# ser = Codec()
# deser = Codec()
# ans = deser.deserialize(ser.serialize(root))

Back

Advanced Trees (Hard) / 244. Level Order Traversal

00:00

1/5

244. Level Order Traversal

Hard

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

1
BFS Approach: Level order traversal is essentially Breadth-First Search (BFS).
2
Queue: Use a queue to keep track of nodes.
3
Level Tracking:
4
Iterate while the queue is not empty.
5
Get the current size of the queue (number of nodes in the current level).
6
Iterate through that number of nodes, processing them and adding their children to the queue.
7
Store the values of the current level in a list.
8
Result: Append each level's list to the final result.

PYTHON PLAYGROUND

⏳ Loading editor…