Height of Binary Tree — Off-by-One Crashed AVL

// A single node in a binary tree.
// Each node holds a value and optional references to a left and right child.
public class BinaryTreeNode {

    int value;                  // The data stored at this node
    BinaryTreeNode leftChild;   // Reference to the left subtree (null if none)
    BinaryTreeNode rightChild;  // Reference to the right subtree (null if none)

    // Constructor: create a new node with a value and no children yet
    public BinaryTreeNode(int value) {
        this.value = value;
        this.leftChild = null;
        this.rightChild = null;
    }

    // Helper method so we can print a node nicely (useful for debugging)
    @Override
    public String toString() {
        return "Node(" + value + ")";
    }

    // --- Build the example tree from the article ---
    public static BinaryTreeNode buildExampleTree() {
        //          10
        //         /  \
        //        5    20
        //       / \     \
        //      3   7    25
        //     /
        //    1

        BinaryTreeNode root    = new BinaryTreeNode(10);
        BinaryTreeNode node5   = new BinaryTreeNode(5);
        BinaryTreeNode node20  = new BinaryTreeNode(20);
        BinaryTreeNode node3   = new BinaryTreeNode(3);
        BinaryTreeNode node7   = new BinaryTreeNode(7);
        BinaryTreeNode node25  = new BinaryTreeNode(25);
        BinaryTreeNode node1   = new BinaryTreeNode(1);

        root.leftChild          = node5;   // 10's left child is 5
        root.rightChild         = node20;  // 10's right child is 20
        node5.leftChild         = node3;   // 5's left child is 3
        node5.rightChild        = node7;   // 5's right child is 7
        node20.rightChild       = node25;  // 20's right child is 25
        node3.leftChild         = node1;   // 3's left child is 1

        return root; // hand back the top of the tree
    }

    public static void main(String[] args) {
        BinaryTreeNode root = buildExampleTree();
        System.out.println("Root node: " + root);
        System.out.println("Root's left child: " + root.leftChild);
        System.out.println("Root's right child: " + root.rightChild);
        System.out.println("Deepest leaf: " + root.leftChild.leftChild.leftChild);
    }
}

public class NodeDepthFinder {

    // Finds the depth of the node containing 'targetValue' in the tree.
    // 'currentNode'  — the node we are currently visiting
    // 'targetValue'  — the value we are searching for
    // 'currentDepth' — how many edges we have already travelled from the root
    //
    // Returns -1 if the value is not found in the tree.
    public static int findDepth(BinaryTreeNode currentNode, int targetValue, int currentDepth) {

        // Base case 1: we fell off the edge of the tree — node doesn't exist
        if (currentNode == null) {
            return -1; // signal that we couldn't find the target
        }

        // Base case 2: we found the target node!
        if (currentNode.value == targetValue) {
            return currentDepth; // the depth is however far we've already travelled
        }

        // Recursive case: search the left subtree first
        int depthInLeftSubtree = findDepth(currentNode.leftChild, targetValue, currentDepth + 1);

        // If left subtree found it, no need to check right subtree
        if (depthInLeftSubtree != -1) {
            return depthInLeftSubtree;
        }

        // Otherwise, search the right subtree
        return findDepth(currentNode.rightChild, targetValue, currentDepth + 1);
    }

    public static void main(String[] args) {
        BinaryTreeNode root = BinaryTreeNode.buildExampleTree();

        // Test every node in our example tree
        int[] valuesToCheck = {10, 5, 20, 3, 7, 25, 1};

        System.out.println("Node Value | Depth");
        System.out.println("-----------|------");

        for (int value : valuesToCheck) {
            // Always start the search from the root at depth 0
            int depth = findDepth(root, value, 0);
            System.out.printf("    %2d     |   %d%n", value, depth);
        }

        // What happens when we search for a value that isn't in the tree?
        int missingDepth = findDepth(root, 99, 0);
        System.out.println("\nDepth of missing node (99): " + missingDepth);
    }
}

public class TreeHeightCalculator {

    // Calculates the height of any given node.
    // Height = number of edges on the LONGEST path from this node to a leaf below it.
    //
    // Key insight: a null node has height -1 by convention.
    // This makes a single leaf node correctly return height 0:
    //   height(leaf) = 1 + max(-1, -1) = 1 + (-1) = 0  ✓
    public static int calculateHeight(BinaryTreeNode node) {

        // Base case: null means we've gone past a leaf — define as -1
        if (node == null) {
            return -1;
        }

        // Recursively find the height of the left subtree
        int leftSubtreeHeight  = calculateHeight(node.leftChild);

        // Recursively find the height of the right subtree
        int rightSubtreeHeight = calculateHeight(node.rightChild);

        // This node's height = 1 edge to the taller child + that child's height
        int tallestChildHeight = Math.max(leftSubtreeHeight, rightSubtreeHeight);

        return 1 + tallestChildHeight;
    }

    public static void main(String[] args) {
        BinaryTreeNode root = BinaryTreeNode.buildExampleTree();

        // Height of the whole tree (measured from root)
        int treeHeight = calculateHeight(root);
        System.out.println("Height of the entire tree: " + treeHeight);

        // Individual node heights
        System.out.println("\nNode Value | Height");
        System.out.println("-----------|-------");
        System.out.printf("    %2d     |   %d  (root — tallest point)%n",   root.value,                                   calculateHeight(root));
        System.out.printf("    %2d     |   %d  (has subtree of depth 2)%n", root.leftChild.value,                         calculateHeight(root.leftChild));
        System.out.printf("    %2d     |   %d  (only one child below it)%n",root.rightChild.value,                        calculateHeight(root.rightChild));
        System.out.printf("    %2d     |   %d  (one leaf child below it)%n",root.leftChild.leftChild.value,               calculateHeight(root.leftChild.leftChild));
        System.out.printf("    %2d     |   %d  (leaf — no children)%n",     root.leftChild.leftChild.leftChild.value,     calculateHeight(root.leftChild.leftChild.leftChild));
        System.out.printf("    %2d     |   %d  (leaf — no children)%n",     root.leftChild.rightChild.value,              calculateHeight(root.leftChild.rightChild));
        System.out.printf("    %2d     |   %d  (leaf — no children)%n",     root.rightChild.rightChild.value,             calculateHeight(root.rightChild.rightChild));

        // Edge case: what is the height of an empty tree?
        int emptyTreeHeight = calculateHeight(null);
        System.out.println("\nHeight of an empty tree (null root): " + emptyTreeHeight);
    }
}

// Complete, self-contained demo.
// Builds the example tree and prints a full depth + height table.
public class HeightAndDepthDemo {

    // ── Node Definition ───────────────────────────────────────────
    static class TreeNode {
        int value;
        TreeNode left, right;

        TreeNode(int value) {
            this.value = value;
        }
    }

    // ── Tree Builder ───────────────────────────────────────────────
    //       10
    //      /  \
    //     5    20
    //    / \     \
    //   3   7    25
    //  /
    // 1
    static TreeNode buildTree() {
        TreeNode root   = new TreeNode(10);
        root.left       = new TreeNode(5);
        root.right      = new TreeNode(20);
        root.left.left  = new TreeNode(3);
        root.left.right = new TreeNode(7);
        root.right.right= new TreeNode(25);
        root.left.left.left = new TreeNode(1);
        return root;
    }

    // ── Height Calculation ─────────────────────────────────────────
    // Returns -1 for null (so a leaf correctly gets height 0)
    static int height(TreeNode node) {
        if (node == null) return -1;
        return 1 + Math.max(height(node.left), height(node.right));
    }

    // ── Depth Calculation ──────────────────────────────────────────
    // Returns -1 if targetValue is not found anywhere in the tree
    static int depth(TreeNode node, int targetValue, int currentDepth) {
        if (node == null)               return -1;            // not found
        if (node.value == targetValue)  return currentDepth;  // found it!

        int leftResult = depth(node.left,  targetValue, currentDepth + 1);
        if (leftResult != -1) return leftResult; // found in left subtree

        return depth(node.right, targetValue, currentDepth + 1); // try right
    }

    // ── Main ───────────────────────────────────────────────────────
    public static void main(String[] args) {
        TreeNode root = buildTree();

        int treeHeight = height(root);
        System.out.println("=== Binary Tree: Height and Depth Summary ===");
        System.out.println("Overall tree height: " + treeHeight + " edges");
        System.out.println();
        System.out.printf("%-12s %-8s %-8s %-10s%n", "Node Value", "Depth", "Height", "Depth+Height");
        System.out.println("----------------------------------------------");

        // All node values in our tree
        int[] allValues = {10, 5, 20, 3, 7, 25, 1};

        for (int val : allValues) {
            int d = depth(root, val, 0);   // depth from root
            int h = height(findNode(root, val)); // height from this node down
            System.out.printf("%-12d %-8d %-8d %-10d%n", val, d, h, d + h);
        }

        System.out.println("----------------------------------------------");
        System.out.println("Notice: depth + height = " + treeHeight + " for all nodes on the longest path.");
    }

    // Helper: returns the TreeNode with the given value (simple DFS search)
    static TreeNode findNode(TreeNode node, int targetValue) {
        if (node == null)              return null;
        if (node.value == targetValue) return node;
        TreeNode leftResult = findNode(node.left, targetValue);
        return (leftResult != null) ? leftResult : findNode(node.right, targetValue);
    }
}