Building a Maximum Binary Tree

The algorithm constructs a binary tree from an integer array with distinct elemnets by recursively selecting the maximum value as the root. The process involves finding the largest element within the current array segment to create a node, then recursively applying the same logic to the left and right subarrays.

Implementation Details

A recursive helper function typically uses start and end indices to define the current subarray segment. Base cases handle empty segments and single-element segments.

class Solution {
    public TreeNode buildMaxTree(int[] values) {
        return build(values, 0, values.length);
    }

    private TreeNode build(int[] arr, int startIdx, int endIdx) {
        if (endIdx - startIdx <= 0) return null;
        if (endIdx - startIdx == 1) return new TreeNode(arr[startIdx]);

        int maxIdx = startIdx;
        for (int i = startIdx + 1; i < endIdx; i++) {
            if (arr[i] > arr[maxIdx]) maxIdx = i;
        }
        TreeNode node = new TreeNode(arr[maxIdx]);
        node.left = build(arr, startIdx, maxIdx);
        node.right = build(arr, maxIdx + 1, endIdx);
        return node;
    }
}

class TreeNode {
    int value;
    TreeNode leftChild;
    TreeNode rightChild;
    TreeNode(int v) { value = v; }
}

Merging Two Binary Trees

Given two binary trees, merge them by summing corresponding node values. If a node exists in one tree but not the other, the existing node becomes part of the resulting tree.

Recursive Approach

class Solution {
    public TreeNode combineTrees(TreeNode t1, TreeNode t2) {
        if (t1 == null) return t2;
        if (t2 == null) return t1;
        t1.value += t2.value;
        t1.leftChild = combineTrees(t1.leftChild, t2.leftChild);
        t1.rightChild = combineTrees(t1.rightChild, t2.rightChild);
        return t1;
    }
}

Searching in a Binary Search Tree

A Binary Search Tree (BST) is ordered such that left subtree values are less than the root, and right subtree values are greater. This property allows efficient, directioanl searches.

Recursive Search Implementation

class Solution {
    public TreeNode findInBST(TreeNode root, int target) {
        if (root == null || root.value == target) return root;
        if (root.value > target) {
            return findInBST(root.leftChild, target);
        } else {
            return findInBST(root.rightChild, target);
        }
    }
}

Validating a Binary Search Tree

To verify if a binary tree is a valid BST, one must ensure that for every node, its value is greater than all values in its left subtree and less than all values in its right subtree.

Using In-Order Traversal for Validation

An in-order traversal of a valid BST yields a strictly increasing sequence of values.

class Solution {
    private TreeNode previous;

    public boolean isBinarySearchTree(TreeNode root) {
        previous = null;
        return validate(root);
    }

    private boolean validate(TreeNode node) {
        if (node == null) return true;
        boolean leftValid = validate(node.leftChild);
        if (!leftValid) return false;
        if (previous != null && node.value <= previous.value) return false;
        previous = node;
        boolean rightValid = validate(node.rightChild);
        return rightValid;
    }
}