1/*
2 * Copyright (c) 2022-2024 Huawei Device Co., Ltd.
3 * Licensed under the Apache License, Version 2.0 (the "License");
4 * you may not use this file except in compliance with the License.
5 * You may obtain a copy of the License at
6 *
7 * http://www.apache.org/licenses/LICENSE-2.0
8 *
9 * Unless required by applicable law or agreed to in writing, software
10 * distributed under the License is distributed on an "AS IS" BASIS,
11 * WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
12 * See the License for the specific language governing permissions and
13 * limitations under the License.
14 */
15
16class TreeNode {
17  private left: TreeNode | null;
18  private right: TreeNode | null;
19  private item: int;
20
21  constructor(left: TreeNode | null, right: TreeNode | null, item: int) {
22    this.left = left;
23    this.right = right;
24    this.item = item;
25  }
26
27  public itemCheck(): int {
28    if (this.left == null)
29      return this.item;
30    else
31      return this.item + this.left!.itemCheck() - this.right!.itemCheck();
32  }
33}
34
35export class AccessBinaryTrees {
36  static readonly startDepth = 4;
37  static readonly endDepth = 7;
38  static readonly expected = -4;
39
40  static bottomUpTree(item: int, depth: int): TreeNode {
41   if (depth > 0) {
42     return new TreeNode(
43       AccessBinaryTrees.bottomUpTree(2*item - 1, depth-1),
44       AccessBinaryTrees.bottomUpTree(2*item, depth-1),
45       item
46     );
47   }
48   return new TreeNode(null, null, item);
49  }
50
51  public run(): void {
52    let ret: int = 0;
53
54    for (let n: int = AccessBinaryTrees.startDepth; n <= AccessBinaryTrees.endDepth; n++) {
55      let minDepth: int = AccessBinaryTrees.startDepth;
56      let maxDepth: int = max(minDepth + 2, n);
57      let stretchDepth: int = maxDepth + 1;
58      let check: int = AccessBinaryTrees.bottomUpTree(0, stretchDepth).itemCheck();
59
60      let longLivedTree = AccessBinaryTrees.bottomUpTree(0, maxDepth);
61
62      for (let depth = minDepth; depth <= maxDepth; depth += 2) {
63        let iterations: int = 1 << (maxDepth - depth + minDepth);
64
65        check = 0;
66        for (let i: int = 1; i <= iterations; i++) {
67          check += AccessBinaryTrees.bottomUpTree(i, depth).itemCheck();
68          check += AccessBinaryTrees.bottomUpTree(-i, depth).itemCheck();
69        }
70      }
71
72      ret += longLivedTree.itemCheck();
73    }
74
75    assert ret == AccessBinaryTrees.expected: "Incorrect result"
76  }
77}
78
79function main(): void {
80  let a = new AccessBinaryTrees;
81  a.run();
82}
83