Problem

You are given a binary tree in a peculiar string representation. Each node is written in the form (lr), where l corresponds to the left child and r corresponds to the right child.

If either l or r is null, it will be represented as a zero. Otherwise, it will be represented by a new (lr) pair.

Here are a few examples:

  • A root node with no children: (00)
  • A root node with two children: ((00)(00))
  • An unbalanced tree with three consecutive left children: ((((00)0)0)0)

Given this representation, determine the depth of the tree.

Examples

Example 1

1
2
3

Input: "(00)"
Output: 1
Explanation: This represents a root node with no children, so the depth is 1.

Example 2

1
2
3

Input: "((00)(00))"
Output: 2
Explanation: This represents a root with two leaf children, so the depth is 2.

Example 3

1
2
3

Input: "((((00)0)0)0)"
Output: 4
Explanation: This represents an unbalanced tree with four consecutive left children, so the depth is 4.

Example 4

1
2
3

Input: "(((00)0)((00)0))"
Output: 3
Explanation: This represents a tree where both left and right subtrees have depth 2, making total depth 3.

Solution

Method 1 - Recursive Parsing

Intuition

The key insight is to parse the string representation recursively. Each (lr) pattern represents a node, where l and r are either 0 (null) or another (lr) pattern (subtree). The depth of a tree is 1 plus the maximum depth of its left and right subtrees.

Approach

  1. Base Case: If we encounter 0, it represents null, so return depth 0
  2. Parse Node: When we see (, we know a node starts, so we parse its left and right children
  3. Recursive Depth: For each child that isn’t null, recursively calculate its depth
  4. Calculate Result: Return 1 + maximum depth of left and right subtrees
  5. Parsing Logic: Use an index pointer to traverse the string and parse each component

Code

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25

class Solution {
public:
    int maxDepth(string s) {
        int idx = 0;
        return parseDepth(s, idx);
    }
    
private:
    int parseDepth(const string& s, int& idx) {
        if (idx >= s.length() || s[idx] == '0') {
            if (s[idx] == '0') idx++;
            return 0;
        }
        
        if (s[idx] == '(') {
            idx++; // skip '('
            int leftDepth = parseDepth(s, idx);
            int rightDepth = parseDepth(s, idx);
            idx++; // skip ')'
            return 1 + max(leftDepth, rightDepth);
        }
        
        return 0;
    }
};
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30

func maxDepth(s string) int {
    idx := 0
    return parseDepth(s, &idx)
}

func parseDepth(s string, idx *int) int {
    if *idx >= len(s) || s[*idx] == '0' {
        if *idx < len(s) && s[*idx] == '0' {
            *idx++
        }
        return 0
    }
    
    if s[*idx] == '(' {
        *idx++ // skip '('
        leftDepth := parseDepth(s, idx)
        rightDepth := parseDepth(s, idx)
        *idx++ // skip ')'
        return 1 + max(leftDepth, rightDepth)
    }
    
    return 0
}

func max(a, b int) int {
    if a > b {
        return a
    }
    return b
}
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27

class Solution {
    private int idx = 0;
    
    public int maxDepth(String s) {
        idx = 0;
        return parseDepth(s);
    }
    
    private int parseDepth(String s) {
        if (idx >= s.length() || s.charAt(idx) == '0') {
            if (idx < s.length() && s.charAt(idx) == '0') {
                idx++;
            }
            return 0;
        }
        
        if (s.charAt(idx) == '(') {
            idx++; // skip '('
            int leftDepth = parseDepth(s);
            int rightDepth = parseDepth(s);
            idx++; // skip ')'
            return 1 + Math.max(leftDepth, rightDepth);
        }
        
        return 0;
    }
}
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19

class Solution:
    def maxDepth(self, s: str) -> int:
        self.idx = 0
        return self.parseDepth(s)
    
    def parseDepth(self, s: str) -> int:
        if self.idx >= len(s) or s[self.idx] == '0':
            if self.idx < len(s) and s[self.idx] == '0':
                self.idx += 1
            return 0
        
        if s[self.idx] == '(':
            self.idx += 1  # skip '('
            leftDepth = self.parseDepth(s)
            rightDepth = self.parseDepth(s)
            self.idx += 1  # skip ')'
            return 1 + max(leftDepth, rightDepth)
        
        return 0

Complexity

  • ⏰ Time complexity: O(n), where n is the length of the string. We visit each character exactly once during parsing.
  • 🧺 Space complexity: O(h), where h is the height of the tree. This is due to the recursive call stack, which can go as deep as the tree height.

Method 2 - Stack-based Parsing

Intuition

Instead of using recursion, we can use a stack to track the depth at each level. When we encounter (, we’re entering a new node, so we push the current depth + 1. When we encounter ), we’re exiting a node, so we pop from the stack. We track the maximum depth seen so far.

Approach

  1. Initialize: Use a stack to track depths and a variable for maximum depth
  2. Parse Characters: Iterate through each character in the string
  3. Handle Opening: When we see (, increment current depth and push to stack
  4. Handle Closing: When we see ), pop from stack to return to parent level
  5. Handle Null: When we see 0, it doesn’t affect depth calculation
  6. Track Maximum: Update maximum depth whenever we push a new depth

Code

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22

class Solution {
public:
    int maxDepth(string s) {
        stack<int> st;
        int maxD = 0, currD = 0;
        
        for (char c : s) {
            if (c == '(') {
                currD++;
                st.push(currD);
                maxD = max(maxD, currD);
            } else if (c == ')') {
                if (!st.empty()) {
                    st.pop();
                    currD = st.empty() ? 0 : st.top();
                }
            }
        }
        
        return maxD;
    }
};
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25

func maxDepth(s string) int {
    var stack []int
    maxD, currD := 0, 0
    
    for _, c := range s {
        if c == '(' {
            currD++
            stack = append(stack, currD)
            if currD > maxD {
                maxD = currD
            }
        } else if c == ')' {
            if len(stack) > 0 {
                stack = stack[:len(stack)-1]
                if len(stack) == 0 {
                    currD = 0
                } else {
                    currD = stack[len(stack)-1]
                }
            }
        }
    }
    
    return maxD
}
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21

class Solution {
    public int maxDepth(String s) {
        Stack<Integer> st = new Stack<>();
        int maxD = 0, currD = 0;
        
        for (char c : s.toCharArray()) {
            if (c == '(') {
                currD++;
                st.push(currD);
                maxD = Math.max(maxD, currD);
            } else if (c == ')') {
                if (!st.isEmpty()) {
                    st.pop();
                    currD = st.isEmpty() ? 0 : st.peek();
                }
            }
        }
        
        return maxD;
    }
}
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16

class Solution:
    def maxDepth(self, s: str) -> int:
        stack = []
        maxD = currD = 0
        
        for c in s:
            if c == '(':
                currD += 1
                stack.append(currD)
                maxD = max(maxD, currD)
            elif c == ')':
                if stack:
                    stack.pop()
                    currD = stack[-1] if stack else 0
        
        return maxD

Complexity

  • ⏰ Time complexity: O(n), where n is the length of the string. We iterate through each character once.
  • 🧺 Space complexity: O(h), where h is the height of the tree. The stack stores at most h elements corresponding to the depth of nested parentheses.

Method 3 - Counter-based Approach

Intuition

We can solve this even more simply by just counting the nesting level of parentheses. Each ( increases the current depth, each ) decreases it, and we track the maximum depth reached. This works because the string representation directly corresponds to the tree structure.

Approach

  1. Initialize: Set current depth and maximum depth to 0
  2. Process Characters: Iterate through each character in the string
  3. Increment on Open: When we see (, increment current depth
  4. Track Maximum: Update maximum depth if current depth exceeds it
  5. Decrement on Close: When we see ), decrement current depth
  6. Ignore Zeros: The 0 characters don’t affect depth calculation

Code

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17

class Solution {
public:
    int maxDepth(string s) {
        int currD = 0, maxD = 0;
        
        for (char c : s) {
            if (c == '(') {
                currD++;
                maxD = max(maxD, currD);
            } else if (c == ')') {
                currD--;
            }
        }
        
        return maxD;
    }
};
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16

func maxDepth(s string) int {
    currD, maxD := 0, 0
    
    for _, c := range s {
        if c == '(' {
            currD++
            if currD > maxD {
                maxD = currD
            }
        } else if c == ')' {
            currD--
        }
    }
    
    return maxD
}
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16

class Solution {
    public int maxDepth(String s) {
        int currD = 0, maxD = 0;
        
        for (char c : s.toCharArray()) {
            if (c == '(') {
                currD++;
                maxD = Math.max(maxD, currD);
            } else if (c == ')') {
                currD--;
            }
        }
        
        return maxD;
    }
}
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12

class Solution:
    def maxDepth(self, s: str) -> int:
        currD = maxD = 0
        
        for c in s:
            if c == '(':
                currD += 1
                maxD = max(maxD, currD)
            elif c == ')':
                currD -= 1
        
        return maxD

Complexity

  • ⏰ Time complexity: O(n), where n is the length of the string. We make a single pass through the string.
  • 🧺 Space complexity: O(1), as we only use a constant amount of extra space for the counters.