Balanced Binary Tree

You are given the relationships between nodes in a binary tree. Each relationship is given as a triple (parent, child, direction). The direction is either 'L' (left child) or 'R' (right child).

Your task is to reconstruct the binary tree and determine if it is balanced. A binary tree is balanced if for every node the absolute difference between the heights of its left and right subtrees is at most 1, i.e., $$|\text{height}(\text{left}) - \text{height}(\text{right})| \le 1.$$

If the tree is empty, consider it balanced.

inputFormat

The first line contains an integer n denoting the number of edges in the tree. If n is 0, then the tree is empty.

The following n lines each contain two integers and a character separated by spaces: parent child direction. The field direction is either 'L' or 'R', indicating whether child is the left or right child of parent.

outputFormat

Output a single line: True if the tree is balanced, and False otherwise.

5
1 2 L
1 3 R
2 4 L
2 5 R
3 6 L

True