Code Logo

Tree Maximum Depth

Published at25 Jul 2026
Created by
Tree Traversal Easy 1 views
Like0

Given a string of parentheses representing a tree structure, find the maximum nesting depth. An opening parenthesis '(' represents going deeper into the tree, and a closing parenthesis ')' represents coming back up. The depth is the maximum number of open parentheses at any point.

For example, the string "(()(()))" has maximum depth 3 because the deepest nesting has three open parentheses. The string "()" has depth 1. An empty string has depth 0. A string like "((()))" has depth 3, and "()()" has depth 1 because parentheses are never nested.

This is a classic stack-based problem that simulates tree traversal without explicitly building a tree. Each '(' pushes a level deeper, and each ')' pops back up. The maximum stack size during this process equals the tree's height. This technique is used in validating HTML/XML structure, parsing mathematical expressions, and evaluating code block nesting.

The algorithm iterates through the string character by character. Initialize a counter to 0 and a max counter to 0. For each '(' increment the counter; for each ')' decrement it. Update the max counter when the current counter exceeds it. At the end, return the max counter.

Edge cases include empty strings (return 0), strings with only opening parentheses like "(((" (the depth equals the length), and strings where closing parentheses never make the counter negative (the input is guaranteed balanced).

Example Input & Output

Example 1
Input
"(()())"
Output
2
Example 2
Input
"()"
Output
1
Example 3
Input
""
Output
0
Example 4
Input
"((()))"
Output
3
Example 5
Input
"(())()"
Output
2

Algorithm Flow

Recommendation Algorithm Flow for Tree Maximum Depth

Solution Approach

Use a counter to track current depth and a variable to track maximum depth.

function solution(s) {
  var depth = 0, maxDepth = 0;
  for (var i = 0; i < s.length; i++) {
    if (s.charAt(i) === '(') { depth++; if (depth > maxDepth) maxDepth = depth; }
    else if (s.charAt(i) === ')') { depth--; }
  }
  return maxDepth;
}

Initialize both depth and maxDepth to 0. Loop through each character. When encountering '(', increment depth and update maxDepth if current depth exceeds it. When encountering ')', decrement depth. After the loop, return maxDepth.

This solution uses O(n) time (one pass through the string) and O(1) space (only two integer variables). No stack data structure is needed since we only track the depth counter, not the actual values.

Best Answers

java
class Solution {
    public int solution(String s) {
        int m=0,c=0;
        for(int i=0;i<s.length();i++){if(s.charAt(i)=='('){c++;m=Math.max(m,c);}else c--;}
        return m;
    }
}