1. Verifying Identical Binary Trees

Given two binary trees, determine if they are structurally identical with matching node values at every position. Empty trees are considered identical.

Analysis: The solution requires recursive comparison of corresponding nodes. When both nodes are null, they match. If one node exists while the other doesn't, the trees differ. For non-null nodes, values must match and both left/right subtrees must recursively satisfy the same condition.

Implementation:

public class TreeComparator {
    public boolean areIdentical(TreeNode firstNode, TreeNode secondNode) {
        if (firstNode == null) return secondNode == null;
        if (secondNode == null) return false;
        if (firstNode.value != secondNode.value) return false;
        return areIdentical(firstNode.left, secondNode.left) && 
               areIdentical(firstNode.right, secondNode.right);
    }
}

2. Subtree Verification in Binary Trees

Determine if one binary tree is a subtree of another, where a subtree includes a node and all its descendants. A tree is considered its own subtree.

Analysis: The approach checks if the current node matches the subtree root. If not, it recursively searches left and right subtrees. When a potential match is found, the identical tree verification method (Problem 1) confirms the subtree relationship.

Implementation:

public class SubtreeChecker {
    public boolean containsSubtree(TreeNode mainTree, TreeNode candidate) {
        if (mainTree == null) return false;
        if (areIdentical(mainTree, candidate)) return true;
        return containsSubtree(mainTree.left, candidate) || 
               containsSubtree(mainTree.right, candidate);
    }

    private boolean areIdentical(TreeNode a, TreeNode b) {
        if (a == null || b == null) return a == b;
        if (a.value != b.value) return false;
        return areIdentical(a.left, b.left) && areIdentical(a.right, b.right);
    }
}

3. Binary Tree Inversion

Transform a binary tree by swapping all left and right child nodes at every level.

Analysis: Using preorder traversal, each node's children are swapped before processing subtrees. The operation propagates recursively from root to leaves, reconstructing the tree with mirrored structure.

Implementation:

public class TreeInverter {
    public TreeNode flipTree(TreeNode root) {
        if (root == null) return null;
        // Swap children directly without helper method
        TreeNode temp = root.left;
        root.left = root.right;
        root.right = temp;
        flipTree(root.left);
        flipTree(root.right);
        return root;
    }
}

4. Symmetric Tree Validation

Check if a binary tree is mirror-symmetric around its center, requiring identical structure and values in mirrored positions.

Analysis: Symmetry verification compares left and right subtrees recursively. The left subtree's left branch must match the right subtree's right branch, while the left subtree's right branch must match the right subtree's left branch, with all corresponding node values matching.

Implementation:

public class SymmetryValidator {
    public boolean isMirrorTree(TreeNode root) {
        if (root == null) return true;
        return compareBranches(root.left, root.right);
    }

    private boolean compareBranches(TreeNode leftBranch, TreeNode rightBranch) {
        if (leftBranch == null || rightBranch == null) return leftBranch == rightBranch;
        if (leftBranch.value != rightBranch.value) return false;
        return compareBranches(leftBranch.left, rightBranch.right) &&
               compareBranches(leftBranch.right, rightBranch.left);
    }
}

5. Balanced Binary Tree Verification

Determine if a binary tree is height-balanced, where every node's subtrees differ in height by at most one.

Analysis: An optimized O(n) approach calculates height while checking balance. During height computation, any imbalance (height difference ≥ 2) triggers immediate negative feedback through the call stack, avoiding redundant calculations.

Implementation:

public class BalanceChecker {
    public boolean isHeightBalanced(TreeNode root) {
        return computeHeight(root) != -1;
    }

    private int computeHeight(TreeNode node) {
        if (node == null) return 0;
        int leftDepth = computeHeight(node.left);
        if (leftDepth == -1) return -1;
        int rightDepth = computeHeight(node.right);
        if (rightDepth == -1) return -1;
        return Math.abs(leftDepth - rightDepth) <= 1 ? 
               Math.max(leftDepth, rightDepth) + 1 : -1;
    }
}

6. BST Conversion to Sorted Doubly Linked List

Transform a binary search tree (BST) into a sorted circular doubly linked list in-place, maintaining ascending order.

Analysis: Leveraging BST's inorder traversal property (yielding sorted sequence), nodes are connected during traversal. Each node's left pointer becomes the previous node reference, while right pointer becomes next node reference. The traversal maintains a trailing pointer to link nodes sequentially.

Implementation:

public class BstConverter {
    private Node lastProcessed;

    public Node convertToCircularList(Node root) {
        if (root == null) return null;
        buildLinks(root);
        Node head = lastProcessed;
        while (head.left != null) head = head.left;
        Node tail = lastProcessed;
        while (tail.right != null) tail = tail.right;
        head.left = tail;
        tail.right = head;
        return head;
    }

    private void buildLinks(Node current) {
        if (current == null) return;
        buildLinks(current.left);
        current.left = lastProcessed;
        if (lastProcessed != null) lastProcessed.right = current;
        lastProcessed = current;
        buildLinks(current.right);
    }
}

7. Tree Construction from Preorder Traversal

Reconstruct a binary tree from a preorder traversal string containing null markers ('#'), then output inorder traversal.

Analysis: The reconstruction uses the preorder sequence with null markers to uniquely determine structure. A static index tracks position during recursive construction. Null markers terminate branches, while valid characters create nodes. The tree is then traversed inorder to produce output.

Implementation:

class TreeNode {
    char data;
    TreeNode left;
    TreeNode right;
    TreeNode(char value) { data = value; }
}

public class TreeBuilder {
    private static int position;

    public static void main(String[] args) {
        Scanner scanner = new Scanner(System.in);
        while (scanner.hasNextLine()) {
            position = 0;
            String sequence = scanner.nextLine();
            TreeNode root = constructTree(sequence);
            printInorder(root);
        }
    }

    private static TreeNode constructTree(String seq) {
        if (seq.charAt(position) == '#') {
            position++;
            return null;
        }
        TreeNode node = new TreeNode(seq.charAt(position++));
        node.left = constructTree(seq);
        node.right = constructTree(seq);
        return node;
    }

    private static void printInorder(TreeNode node) {
        if (node == null) return;
        printInorder(node.left);
        System.out.print(node.data + " ");
        printInorder(node.right);
    }
}