Binary Tree Dimensions

1. Size of a Binary Tree

The size of a binary tree is simply the total number of nodes it contains. This is often the most straightforward property to calculate.

The logic is naturally recursive and follows a divide-and-conquer approach:

• The size of an empty tree (a null node) is 0.
• The size of a non-empty tree is 1 (for the current node) plus the size of its left subtree, plus the size of its right subtree.

This can be expressed with the recurrence relation:
size(node) = 1 + size(node.left) + size(node.right)

To see this logic in action and understand the recursive flow, let's watch a short video.

Java Implementation

The implementation in Java is a direct translation of the recursive formula. It's clean, concise, and elegant.

Here's the essential code:

class TreeNode {
    int val;
    TreeNode left;
    TreeNode right;
    // Constructor
    TreeNode(int val) { this.val = val; }
}

class Solution {
    public int getSize(TreeNode root) {
        // Base case: an empty tree has size 0.
        if (root == null) {
            return 0;
        }

        // Recursive step: 1 (current node) + size of left + size of right.
        int leftSize = getSize(root.left);
        int rightSize = getSize(root.right);
        
        return 1 + leftSize + rightSize;
    }
}

• Time Complexity: O(N), as we must visit every node once.
• Space Complexity: O(H), where H is the height of the tree. This is for the recursion call stack. In the worst case (a skewed tree), this can be O(N). In a balanced tree, it's O(log N).

2. Height of a Binary Tree

The height (or maximum depth) of a binary tree is the length of the longest path from the root node to any leaf node.

There's a slight ambiguity you should be aware of for interviews:

• Height in terms of nodes: The number of nodes on the longest path. An empty tree has height 0. A single-node tree has height 1.
• Height in terms of edges: The number of edges on the longest path. An empty tree has height -1 or 0 (depending on convention). A single-node tree has height 0.

It's always a good idea to clarify which definition the interviewer is using. We will use the number of nodes for our examples, as it often leads to more intuitive base cases.

The recursive logic is similar to calculating size, but instead of summing, we take the maximum:

• The height of an empty tree is 0.
• The height of a non-empty tree is 1 (for the current node) plus the height of its taller subtree (left or right).

Recurrence relation: height(node) = 1 + max(height(node.left), height(node.right))

Java Implementation

The Java code mirrors this logic.

class Solution {
    public int getHeight(TreeNode root) {
        // Base case: height of an empty tree is 0.
        if (root == null) {
            return 0;
        }

        // Recursively find the height of the left and right subtrees.
        int leftHeight = getHeight(root.left);
        int rightHeight = getHeight(root.right);

        // The height of the tree is 1 + the height of the taller subtree.
        return 1 + Math.max(leftHeight, rightHeight);
    }
}

• Time Complexity: O(N), as we visit every node.
• Space Complexity: O(H) for the recursion stack.

public int getHeightInEdges(TreeNode root) {
    if (root == null) {
        return -1; // Base case for edge-based height
    }
    int leftHeight = getHeightInEdges(root.left);
    int rightHeight = getHeightInEdges(root.right);
    return 1 + Math.max(leftHeight, rightHeight);
}

3. Diameter of a Binary Tree

The diameter of a binary tree is the length of the longest path between any two nodes in the tree. This path may or may not pass through the root. This is a classic, slightly more advanced problem built upon the height calculation.

Consider these two scenarios for the longest path:

1. It passes through the root node. In this case, its length is height(left subtree) + height(right subtree) + 1.
2. It is entirely contained within the left or right subtree.

The diameter of the tree is the maximum of these three values:

• The diameter of the left subtree.
• The diameter of the right subtree.
• The longest path passing through the root (1 + height(left) + height(right)).

The O(N²) Approach

A naive solution would be to traverse the tree. For each node, you'd calculate the diameter passing through it by calling getHeight() on its left and right children. You'd keep track of the maximum diameter found.

// Inefficient O(N^2) approach
class Solution_Naive {
    public int diameterOfBinaryTree(TreeNode root) {
        if (root == null) {
            return 0;
        }

        // 1. Diameter passing through the root
        int diameterThroughRoot = getHeight(root.left) + getHeight(root.right); // Assuming height in nodes, path is sum of nodes on each side, root is double counted so we'd need to adjust. A better formula using our node-based height: (getHeight(left) + getHeight(right)).

        // For simplicity let's stick to path length in terms of edges for diameter. Path length = #nodes - 1
        // Path length through root = height(left) + height(right) [if height is #nodes]
        // Let's define height as #nodes. Path length passing through root is height(left) + height(right).
        int pathThroughRoot = getHeight(root.left) + getHeight(root.right);


        // 2. Diameter within the left subtree
        int leftDiameter = diameterOfBinaryTree(root.left);
        
        // 3. Diameter within the right subtree
        int rightDiameter = diameterOfBinaryTree(root.right);

        return Math.max(pathThroughRoot, Math.max(leftDiameter, rightDiameter));
    }
    
    // Helper function from before
    public int getHeight(TreeNode root) {
        if (root == null) return 0;
        return 1 + Math.max(getHeight(root.left), getHeight(root.right));
    }
}

Can you see why this is O(N²)? For each of the N nodes, we call getHeight(), which itself takes O(N) time in the worst case.

The O(N) Approach

We can do much better. The inefficiency comes from repeatedly calculating the height of the same subtrees. We can optimize this by having our recursive function compute both the height and the diameter in a single pass.

The idea is to write a helper function that returns the height of a subtree, but also updates a global or passed-by-reference variable holding the maximum diameter found so far. In Java, a common trick to pass a primitive by reference is to use a single-element array.

Here is the logic for our O(N) helper function, heightAndUpdateDiameter(node, diameter):

1. Base Case: If node is null, return 0 (height of an empty tree).
2. Recursive Step:
   a. Recursively call for the left child to get its height: leftHeight = heightAndUpdateDiameter(node.left, diameter).
   b. Recursively call for the right child to get its height: rightHeight = heightAndUpdateDiameter(node.right, diameter).
3. Update Diameter: Calculate the path length passing through the current node: path = leftHeight + rightHeight. Update the global diameter diameter[0] = Math.max(diameter[0], path).
4. Return Height: Return the height of the subtree rooted at the current node: 1 + Math.max(leftHeight, rightHeight).

Let's implement this efficient approach. Note that diameter is usually measured in edges, so the path length is number of nodes - 1. Our leftHeight + rightHeight calculation naturally gives the number of edges.

class Solution {
    public int diameterOfBinaryTree(TreeNode root) {
        // Use an array of size 1 to pass the diameter by reference.
        int[] diameter = new int[1]; 
        diameter[0] = 0;
        
        heightAndUpdateDiameter(root, diameter);
        
        return diameter[0];
    }

    private int heightAndUpdateDiameter(TreeNode node, int[] diameter) {
        // Base case: Height of an empty tree is 0.
        if (node == null) {
            return 0;
        }

        // Recursively find the height of left and right subtrees.
        // The recursive calls will also update the diameter if a longer path is found in subtrees.
        int leftHeight = heightAndUpdateDiameter(node.left, diameter);
        int rightHeight = heightAndUpdateDiameter(node.right, diameter);

        // Calculate the diameter passing through the current node.
        // It's the sum of the heights of the left and right subtrees.
        int currentDiameter = leftHeight + rightHeight;

        // Update the maximum diameter found so far.
        diameter[0] = Math.max(diameter[0], currentDiameter);

        // Return the height of the current node's subtree.
        return 1 + Math.max(leftHeight, rightHeight);
    }
}

This combined approach visits each node only once, achieving an optimal O(N) time complexity.

Conclusion

In this lesson, you've learned how to compute three critical properties of a binary tree using recursive traversals.

Key Takeaways:

• Size: A simple recursive sum: 1 + size(left) + size(right).
• Height: A recursive "max" operation: 1 + max(height(left), height(right)). Always be mindful of the definition (nodes vs. edges).
• Diameter: The most complex of the three. The key to an efficient O(N) solution is to combine the height and diameter calculations into a single post-order traversal, avoiding redundant computations.

These algorithms are fundamental and demonstrate the power of recursion for solving tree-based problems. The pattern of a function returning a value (like height) while also modifying a shared state (like diameter) is a powerful technique you'll see again.

Preview of the next lesson:
We will continue applying traversal techniques to solve more view-based problems. In the next lesson, you'll learn how to find the left and right views of a binary tree, which involves finding the outermost nodes at each level.