Construct a binary tree from its bracket string representation

Medium

Problem

The string encodes a tree as a value followed by zero, one or two parenthesised subtrees: the first pair is the left child, the second is the right. Build the tree.

Example 1

Input:  "4(2(3)(1))(6(5))"
Output: 4 with left 2 (children 3, 1) and right 6 (left child 5)

Also asked as: Construct Binary Tree from String with Bracket Representation

Test cases

Case 1

Input:    "4(2(3)(1))(6(5))"
Expected: [4,2,6,3,1,5]

Case 2

Input:    "10(20)(30)"
Expected: [10,20,30]

Case 3

Input:    "1(2)"
Expected: [1,2]

Case 4

Input:    "1"
Expected: [1]

Your solution ✓ Solved

Ctrl/⌘ + Enter to run
View solutionHide solution1 approach

1. Recursive descent parser

Time O(n)Space O(h)

A number is a node; an opening "(" begins its left child, a second "(" its right child; ")" closes.

function str2tree(s) {
let i = 0;
const parse = () => {
let sign = 1;
if (s[i] === '-') { sign = -1; i++; }
let num = 0;
while (i < s.length && /\d/.test(s[i])) num = num * 10 + +s[i++];
const node = { val: sign * num, left: null, right: null };
if (s[i] === '(') { i++; node.left = parse(); i++; } // skip '(' and ')'
if (s[i] === '(') { i++; node.right = parse(); i++; }
return node;
};
return s ? parse() : null;
}