Build Quadtree and Find Grid Words

This interview included two algorithm problems. 1. Quad-partition tree: Given an `n x n` binary matrix where `n` is a power of 2, recursively build a tree representation of the matrix. Each node represents a square region. If all cells in the region have the same value, create a leaf node storing that value. Otherwise, create an internal node with four children in this order: top-left, top-right, bottom-left, bottom-right. Return the root node. 2. Find dictionary words in a character board: Given an `m x n` grid of lowercase letters and a list of candidate words, return all words that can be formed by moving horizontally or vertically between adjacent cells. A cell may be used at most once when forming a single word. Return each matching word at most once, in any order. Discuss the expected time and space complexity for both problems.