Construct an N-ary Tree from Balanced Parentheses
I recently encountered this interview problem for oracle IC3 interview:
Given a balanced-parentheses string, construct and return the root of an N-ary tree. Each matching () represents a node, and parentheses directly nested inside it represent its children.
Example:
(()()(()))
A stack-based solution can construct the tree in O(n) time:
- On
(, create a node and add it to the current parent’s children. - Push the new node onto the stack.
- On
), pop the completed node. - Return the first node as the root.
Comments (1)