Skip to content
AITroveRead. Build. Understand.
Reading list
Make this comfortable

Balanced-parentheses trees: encode an ordered hierarchy

Last updated: 5 Oct 20269 min read
tutorial
IntermediateBy AITrove Editorial

A depth-first traversal can encode an ordered rooted tree by writing an opening parenthesis on entry to a node and a closing parenthesis on exit. Every subtree occupies one contiguous balanced interval. Its node count is half the interval length; an ancestor's interval contains every descendant interval. The example builds opening and closing positions and parent links for an organization hierarchy, then answers subtree size and ancestry directly. It finds a lowest common unit by walking parent links from one node and testing ancestors of the other. This is a teaching index with explicit dictionaries; a genuinely succinct representation would pack the bit sequence and add compact rank, select, and matching support.

Operational case

An operations root has dispatch and quality branches. Dispatch owns east and west, while quality owns audit. The encoding is ((()())(())); dispatch spans three nodes and contains east. The lowest common unit for east and audit is operations. Child order affects the encoding even when the parent relationships are unchanged, so writers must define that order before publication. The constructor rejects repeated or unreachable mapped nodes. This index is static: inserting a unit changes positions after it and requires rebuilding the encoding and its maps.

Working Python program

python
class OrganizationParentheses:
    def __init__(self, root_id, children_by_id):
        self.sequence = []
        self.open_at = {}
        self.close_at = {}
        self.parent = {}
        self.labels_at_open = {}
        visited = set()

        def visit(unit_id, parent_id):
            if unit_id in visited:
                raise ValueError("hierarchy must be a tree")
            visited.add(unit_id)
            opening = len(self.sequence)
            self.sequence.append("(")
            self.open_at[unit_id] = opening
            self.labels_at_open[opening] = unit_id
            self.parent[unit_id] = parent_id
            for child_id in children_by_id.get(unit_id, []):
                visit(child_id, unit_id)
            self.close_at[unit_id] = len(self.sequence)
            self.sequence.append(")")

        visit(root_id, None)
        if set(children_by_id) - visited:
            raise ValueError("unreachable hierarchy node")

    def subtree_size(self, unit_id):
        return (self.close_at[unit_id] - self.open_at[unit_id] + 1) // 2

    def contains_descendant(self, ancestor_id, unit_id):
        return (self.open_at[ancestor_id] <= self.open_at[unit_id]
                < self.close_at[unit_id] <= self.close_at[ancestor_id])

    def lowest_common_unit(self, first_id, second_id):
        ancestors = set()
        while first_id is not None:
            ancestors.add(first_id)
            first_id = self.parent[first_id]
        while second_id not in ancestors:
            second_id = self.parent[second_id]
        return second_id


if __name__ == "__main__":
    tree = OrganizationParentheses("operations", {
        "operations": ["dispatch", "quality"],
        "dispatch": ["east", "west"],
        "quality": ["audit"],
    })
    print("encoding:", "".join(tree.sequence))
    print("dispatch subtree:", tree.subtree_size("dispatch"))
    print("east under dispatch:", tree.contains_descendant("dispatch", "east"))
    print("east and audit:", tree.lowest_common_unit("east", "audit"))

Output

Output
encoding: ((()())(()))
dispatch subtree: 3
east under dispatch: True
east and audit: operations

Time, space, and tradeoff

Building the sequence and explicit maps visits N nodes and edges once, using O(N) time and O(N) Python objects. Subtree size and interval-based ancestry are O(1) after construction. This direct lowest-common-unit query takes O(H) time and O(H) temporary set space for hierarchy height H; it does not claim constant-time succinct navigation. Storage is not 2N bits because the example retains strings, dictionaries, and labels. A binary-lifting table is preferable for many common-ancestor queries when O(N log N) auxiliary space is acceptable.

Common Mistakes

  • Do not call an unpacked Python representation succinct.
  • Do not confuse a parenthesis position with a node label.
  • Do not use stale positions after a hierarchy edit.
  • Do not claim this direct parent-walk common-ancestor query is constant time.

Connected lessons

Compare its update and query contract with Linear hashing: split one bucket at a time as a table grows, Compressed 2D Fenwick trees: toggle known points and count rectangles, Persistent two-list queues: fork FIFO dispatch history, then complete the structure audit and decision quiz.

Euler-tour RMQ: answer static common ancestors in constant query time adds a distinct structure contract to compare.

data structures
range-query-structures
Storage details