Height of BST

Problem Statement

Write a Java program that extends a Binary Search Tree (BST) implementation to include a method that computes the height of the tree. The height of a tree is the number of edges on the longest path from the root to a leaf, with an empty tree having a height of -1. The program should reuse the BST node structure and test the height computation with balanced and unbalanced trees, including edge cases like an empty tree and a single-node tree. You can visualize this as measuring the tallest branch of a family tree, counting the number of parent-child connections from the top to the deepest descendant.

Input:

• A binary search tree represented by nodes with integer values. Output: An integer representing the height of the tree, and a string representation of the tree for clarity. Constraints:
• The tree has between 0 and 10^5 nodes.
• Node values are integers in the range [-10^9, 10^9].
• Duplicate values are not allowed in the BST. Example:
• Input: Tree = [5, left: [3, left: [1], right: [4]], right: [7]] (balanced)
• Output: Height = 2, "Preorder: 5 3 1 4 7"
• Explanation: Longest path has 2 edges (e.g., 5→3→1).
• Input: Tree = [5, right: [7, right: [9, right: [10]]] (unbalanced, skewed)
• Output: Height = 3, "Preorder: 5 7 9 10"
• Explanation: Longest path has 3 edges (5→7→9→10).
• Input: Tree = []
• Output: Height = -1, "Empty"
• Explanation: Empty tree has height -1.

Pseudocode

CLASS Node
    SET value to integer
    SET left to Node (null by default)
    SET right to Node (null by default)
ENDCLASS

FUNCTION getHeight(root)
    IF root is null THEN
        RETURN -1
    ENDIF
    SET leftHeight to getHeight(root.left)
    SET rightHeight to getHeight(root.right)
    RETURN maximum of leftHeight, rightHeight plus 1
ENDFUNCTION

FUNCTION toString(root)
    IF root is null THEN
        RETURN "Empty"
    ENDIF
    CREATE result as new StringBuilder
    FUNCTION preorder(node)
        IF node is null THEN
            RETURN
        ENDIF
        APPEND node.value and " " to result
        CALL preorder(node.left)
        CALL preorder(node.right)
    ENDFUNCTION
    CALL preorder(root)
    RETURN "Preorder: " + result as string
ENDFUNCTION

FUNCTION main()
    SET testCases to array of trees
    FOR each testCase in testCases
        PRINT test case details
        CALL getHeight(testCase.root)
        PRINT height and tree using toString
    ENDFOR
ENDFUNCTION

Algorithm Steps

1. Reuse the Node class with: a. An integer value. b. left and right pointers to child nodes.
2. Define getHeight: a. If root is null, return -1. b. Recursively compute the height of the left subtree. c. Recursively compute the height of the right subtree. d. Return the maximum of left and right heights plus 1.
3. Define toString: a. If root is null, return "Empty". b. Perform preorder traversal, appending values to a string.
4. In main, test with: a. A balanced BST (e.g., complete binary tree). b. An unbalanced BST (e.g., skewed tree). c. An empty tree. d. A single-node tree.

Java Implementation

public class HeightOfBST {
    // Node class for the binary search tree
    static class Node {
        int value;
        Node left, right;

        Node(int value) {
            this.value = value;
            this.left = null;
            this.right = null;
        }
    }

    // Computes the height of the BST
    public int getHeight(Node root) {
        if (root == null) {
            return -1;
        }
        int leftHeight = getHeight(root.left);
        int rightHeight = getHeight(root.right);
        return Math.max(leftHeight, rightHeight) + 1;
    }

    // Converts tree to string (preorder traversal)
    public String toString(Node root) {
        if (root == null) {
            return "Empty";
        }
        StringBuilder result = new StringBuilder();
        preorder(root, result);
        return "Preorder: " + result.toString().trim();
    }

    private void preorder(Node node, StringBuilder result) {
        if (node == null) {
            return;
        }
        result.append(node.value).append(" ");
        preorder(node.left, result);
        preorder(node.right, result);
    }

    // Helper class for test cases
    static class TestCase {
        Node root;

        TestCase(int[] values, int[][] edges) {
            if (values.length == 0) {
                root = null;
                return;
            }
            Node[] nodes = new Node[values.length];
            for (int i = 0; i < values.length; i++) {
                nodes[i] = new Node(values[i]);
            }
            for (int[] edge : edges) {
                int parent = edge[0], child = edge[1];
                if (edge[2] == 0) {
                    nodes[parent].left = nodes[child];
                } else {
                    nodes[parent].right = nodes[child];
                }
            }
            root = nodes[0];
        }
    }

    // Main method to test BST height
    public static void main(String[] args) {
        HeightOfBST heightCalculator = new HeightOfBST();

        // Test cases
        TestCase[] testCases = {
            // Balanced BST: [5, left: [3, left: 1, right: 4], right: 7]
            new TestCase(
                new int[]{5, 3, 1, 4, 7},
                new int[][]{{0, 1, 0}, {0, 4, 1}, {1, 2, 0}, {1, 3, 1}}
            ),
            // Unbalanced BST: [5, right: [7, right: [9, right: 10]]]
            new TestCase(
                new int[]{5, 7, 9, 10},
                new int[][]{{0, 1, 1}, {1, 2, 1}, {2, 3, 1}}
            ),
            // Empty tree
            new TestCase(new int[]{}, new int[][]{}),
            // Single node
            new TestCase(new int[]{10}, new int[][]{})
        };

        // Run test cases
        for (int i = 0; i < testCases.length; i++) {
            System.out.println("Test case " + (i + 1) + ":");
            System.out.println("Tree: " + heightCalculator.toString(testCases[i].root));
            int height = heightCalculator.getHeight(testCases[i].root);
            System.out.println("Height: " + height + "\n");
        }
    }
}

Output

Running the main method produces:

Test case 1:
Tree: Preorder: 5 3 1 4 7
Height: 2

Test case 2:
Tree: Preorder: 5 7 9 10
Height: 3

Test case 3:
Tree: Empty
Height: -1

Test case 4:
Tree: Preorder: 10
Height: 0

Explanation:

• Test case 1: Balanced BST with root 5, height 2 (path 5→3→1 or 5→3→4).
• Test case 2: Unbalanced (skewed) BST, height 3 (path 5→7→9→10).
• Test case 3: Empty tree, height -1.
• Test case 4: Single node, height 0 (no edges).

How It Works

• Node: Stores an integer value and pointers to left and right children.
• getHeight:
  • Returns -1 for null nodes (empty tree).
  • Recursively computes heights of left and right subtrees.
  • Returns maximum of left and right heights plus 1.
• toString: Performs preorder traversal, returns space-separated values or "Empty".
• Example Trace (Test case 1):
  • Root=5: leftHeight = getHeight(3), rightHeight = getHeight(7).
  • Node 3: leftHeight = getHeight(1) = 0, rightHeight = getHeight(4) = 0, return max(0, 0) + 1 = 1.
  • Node 7: leftHeight = -1, rightHeight = -1, return max(-1, -1) + 1 = 0.
  • Root: max(1, 0) + 1 = 2.
• Main Method: Tests balanced BST, unbalanced BST, empty tree, and single node.

Complexity Analysis Table

Note:

• n is the number of nodes in the tree.
• h is the height of the tree (O(n) for skewed, O(log n) for balanced).
• Time complexity: O(n) for getHeight and toString (visit each node once).
• Space complexity: O(h) for recursion stack in getHeight and toString.
• Worst case: O(n) time and O(n) space for skewed trees.

✅ Tip: Use recursion to compute the height by taking the maximum of left and right subtree heights. Define empty tree height as -1 to align with edge-counting conventions.

⚠ Warning: Handle null nodes correctly to avoid null pointer exceptions. Be aware that unbalanced trees (e.g., skewed) have higher recursion stack space complexity.