Constructing Binary Trees from Inorder and Preorder Traversals

Given the preorder and inorder traversal sequences of a binary tree, the tree structure can be uniquely reconstructed. The first element in the preorder sequence always represents the root of the current subtree. By locating this root value within the inorder sequence, one can partition the tree into left and right subtrees. Elements situated to the left of the root in the inorder sequence constitute the left subtree, while those to the right constitute the right subtree.

An efficient approach involves utilizing a hash map to store the indices of values from the inorder sequence, allowing for O(1) root position lookups. A global pointer tracks the current position in the preorder sequence. As the algorithm processes each root, it recursively constructs the left subtree followed by the right subtree.

import java.util.HashMap;
import java.util.Map;

class Solution {
    private Map inorderMap;
    private int[] preorderSeq;
    private int preorderIndex;

    public TreeNode buildTree(int[] preorder, int[] inorder) {
        inorderMap = new HashMap<>();
        preorderSeq = preorder;
        preorderIndex = 0;

        for (int i = 0; i < inorder.length; i++) {
            inorderMap.put(inorder[i], i);
        }

        return buildSubTree(0, inorder.length - 1);
    }

    private TreeNode buildSubTree(int leftBound, int rightBound) {
        if (leftBound > rightBound) {
            return null;
        }

        int rootValue = preorderSeq[preorderIndex++];
        TreeNode rootNode = new TreeNode(rootValue);

        int inorderPivot = inorderMap.get(rootValue);

        rootNode.left = buildSubTree(leftBound, inorderPivot - 1);
        rootNode.right = buildSubTree(inorderPivot + 1, rightBound);

        return rootNode;
    }
}

Constructing Binary Trees from Preorder and Postorder Traversals

Reconstructing a binary tree from preorder and postorder traversals differs slightly because multiple tree shapes can yield the same traversal sequences for non-full binary trees. The construction logic assumes that the preorder sequence provides the root, and the subsequent element acts as the root of the left subtree. By locating this left child within the postorder sequence, the size of the left subtree can be determined, enabling the partitioning of both sequences for recursive construction.

import java.util.HashMap;
import java.util.Map;

class Solution {
    private Map postorderMap;
    private int[] preorderSeq;

    public TreeNode constructFromPrePost(int[] preorder, int[] postorder) {
        postorderMap = new HashMap<>();
        preorderSeq = preorder;

        for (int i = 0; i < postorder.length; i++) {
            postorderMap.put(postorder[i], i);
        }

        return construct(0, preorder.length - 1, 0, postorder.length - 1);
    }

    private TreeNode construct(int preStart, int preEnd, int postStart, int postEnd) {
        if (preStart > preEnd) {
            return null;
        }

        TreeNode root = new TreeNode(preorderSeq[preStart]);
        if (preStart == preEnd) {
            return root;
        }

        int leftChildVal = preorderSeq[preStart + 1];
        int leftChildPostIdx = postorderMap.get(leftChildVal);
        int leftSubtreeSize = leftChildPostIdx - postStart + 1;

        root.left = construct(preStart + 1, preStart + leftSubtreeSize, postStart, leftChildPostIdx);
        root.right = construct(preStart + leftSubtreeSize + 1, preEnd, leftChildPostIdx + 1, postEnd - 1);

        return root;
    }
}

Finding the Lowest Common Ancestor in a Binary Search Tree

The Lowest Common Ancestor (LCA) of two nodes in a Binary Search Tree (BST) can be found efficiently by leveraging the BST property: for any given node, all values in its left subtree are smaller, and all values in its right subtree are larger. If both target nodes possess values smaller than the current node, the LCA must lie in the left subtree. Conversely, if both values are larger, the LCA lies in the right subtree. The point where the paths diverge—or where one node is the ancestor of the other—is the LCA.

class Solution {
    public TreeNode lowestCommonAncestor(TreeNode root, TreeNode p, TreeNode q) {
        TreeNode current = root;
        while (current != null) {
            if (p.val < current.val && q.val < current.val) {
                current = current.left;
            } else if (p.val > current.val && q.val > current.val) {
                current = current.right;
            } else {
                return current;
            }
        }
        return null;
    }
}

Minimizing Increments to Equalize Path Costs

To make the sum of values from the root to every leaf node equal with minimum increments, a post-order Depth First Search (DFS) approach is utilized. The logic operates from the bottom up: for any given node, the cost to equalize its left and right branches is the absolute difference between the maximum path sums of the two children. The node then returns the larger of the two path sums plus its own value to its parent. This ensures that the minimum number of increments is added at each step to match the longest path requirement.

class Solution {
    private int totalCost;

    public int minIncrements(int n, int[] cost) {
        totalCost = 0;
        calculateMaxPath(cost, 1);
        return totalCost;
    }

    private int calculateMaxPath(int[] cost, int index) {
        if (index > cost.length) {
            return 0;
        }

        int leftSum = calculateMaxPath(cost, 2 * index);
        int rightSum = calculateMaxPath(cost, 2 * index + 1);

        totalCost += Math.abs(leftSum - rightSum);

        return Math.max(leftSum, rightSum) + cost[index - 1];
    }
}