SQL Query Optimizer (Predicate Pushdown)

Implement a query optimizer that rewrites an SQL Abstract Syntax Tree (AST) to reduce data movement and I/O by pushing filter (WHERE) predicates below join operators and, when beneficial, reordering joins. You are given an AST already parsed into a tree of operator nodes. Each node is one of four types: 1) Scan(tableName) – leaf that produces all rows of that table; 2) Join(left, right, condition) – inner join of two subtrees; 3) Filter(child, predicate) – keeps only rows satisfying the predicate expression; 4) Project(child, columnList) – outputs only the listed columns/expressions. A predicate is “push-downable” past a join if every column it references belongs to one child’s schema. Your task is to write a function optimize(root) -> root that returns a logically equivalent tree with two independent optimizations applied:

1. Predicate push-down: move every Filter node as far down the tree as possible (below joins when safe) so filtering happens before joins.
2. Join reordering: after push-down, reorder sequences of inner joins so that the join estimated to produce the fewest rows is executed first. You may assume a helper estimateRows(node) -> int that gives a cardinality estimate for any subtree; use it to pick the smallest-first order among a left-deep join chain.

The function should run in a single pass over the tree and must preserve query semantics. Return the new root of the optimized tree.