Construct a binary tree from its bracket string representation
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]
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;}