Binary Tree Depth from Parenthesized String Representation
HardUpdated: Aug 12, 2025
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
Input: "(00)"
Output: 1
Explanation: This represents a root node with no children, so the depth is 1.
Example 2
Input: "((00)(00))"
Output: 2
Explanation: This represents a root with two leaf children, so the depth is 2.
Example 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
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
- Base Case: If we encounter
0, it represents null, so return depth 0 - Parse Node: When we see
(, we know a node starts, so we parse its left and right children - Recursive Depth: For each child that isn't null, recursively calculate its depth
- Calculate Result: Return 1 + maximum depth of left and right subtrees
- Parsing Logic: Use an index pointer to traverse the string and parse each component
Code
C++
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;
}
};
Go
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
}
Java
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;
}
}
Python
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
- Initialize: Use a stack to track depths and a variable for maximum depth
- Parse Characters: Iterate through each character in the string
- Handle Opening: When we see
(, increment current depth and push to stack - Handle Closing: When we see
), pop from stack to return to parent level - Handle Null: When we see
0, it doesn't affect depth calculation - Track Maximum: Update maximum depth whenever we push a new depth
Code
C++
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;
}
};
Go
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
}
Java
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;
}
}
Python
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
- Initialize: Set current depth and maximum depth to 0
- Process Characters: Iterate through each character in the string
- Increment on Open: When we see
(, increment current depth - Track Maximum: Update maximum depth if current depth exceeds it
- Decrement on Close: When we see
), decrement current depth - Ignore Zeros: The
0characters don't affect depth calculation
Code
C++
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;
}
};
Go
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
}
Java
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;
}
}
Python
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.