Trees and Binary Search Trees Questions

Tree data structures as tested in coding interviews: binary trees, binary search trees, self-balancing trees (AVL insertion and deletion with rotations, a comparison with red-black trees, and alternatives such as treaps, splay trees and scapegoat trees), tries (prefix trees and radix trees), and N-ary, size-augmented and sum-augmented trees such as order-statistic trees. Covers traversal orders (in/pre/post-order, level-order, zigzag, iterative, generator-based and Morris variants), BST search, insertion and deletion invariants including duplicate-key policies, validation, successor and iterator design, range and kth-smallest queries, lowest common ancestor (including parent pointers, binary lifting and repeated queries on a static tree), tree reconstruction from traversals, serialization formats and parsing, converting between trees and sorted lists or linked lists, height, balance, diameter and path-sum recursion, subtree equality and hashing, persistent and snapshot-consistent trees, and how tree shape drives logarithmic versus degenerate performance. Excludes plain linked-list and stack/queue exercises with no tree in them, tree dynamic programming recurrences, general graph traversal, heap mechanics, and on-disk database index design, which are covered elsewhere.