Comparing Left and Right Branch of a Complete Binary Tree

  • 时间:2020-09-20 14:08:18
  • 分类:网络文摘
  • 阅读:76 次

A complete binary tree is a binary tree that each level except possibiliy the last level, is completed filled. Suppose you are giving a binary tree represented as an array. For example, [3, 6, 2, 9, -1, 10] retpresents the following binary tree, where -1 indicates it is a NULL node.

    3
  6   2
9    10

Write a function that determines whether the left or right branch of the tree is larger. The size of each branch is the sum of the node vlaues. The function should return the string “Right” if the right side is larger and “Left” if the left side is larger. If the tree has zero nodes or if the size of the branches are equal, an empty string “” should be returned.

How to Store/Index a Complete Binary Tree?

We can use an array to index/store a complete binary tree where the root index starts at ONE, and the left child index is always twice its parent index, and the right index is the twice parent index plus one.

For example, in above complete binary tree, the Node 6 has index 2 which is equal to 2*ROOT = 2 * 1. and the Node 2 is 2*ROOT+1 = 2*1+1 = 3.

In the following Javascript method, we have inlined local recursive method that takes the array (complete binary tree) and a node index, which will recursively sum up the nodes in the branch until it gets to the leave nodes.

1
2
3
4
5
6
7
8
9
10
11
12
13
14
const solution = (arr) => {
    if (!arr) return "";
    if (arr.length === 0) return "";    
    const sum = (arr, idx) => {
        if (idx - 1 < arr.length) {
            if (arr[idx - 1] === -1) return 0;
            return arr[idx - 1] + sum(arr, idx * 2) + sum(arr, idx * 2 + 1);
        }
        return 0;
    };
    const left = sum(arr, 2);
    const right = sum(arr, 3);
    return (left == right) ? "" : (left > right ? "Left" : "Right");
};
const solution = (arr) => {
    if (!arr) return "";
    if (arr.length === 0) return "";    
    const sum = (arr, idx) => {
        if (idx - 1 < arr.length) {
            if (arr[idx - 1] === -1) return 0;
            return arr[idx - 1] + sum(arr, idx * 2) + sum(arr, idx * 2 + 1);
        }
        return 0;
    };
    const left = sum(arr, 2);
    const right = sum(arr, 3);
    return (left == right) ? "" : (left > right ? "Left" : "Right");
};

Then we can simply call the function twice to compute the sum for left and right branch respectively. The time complexity is O(N) where N is the number of the nodes in the complete binary tree. And the space complexity is O(logN) because the recursion implies a call stack, and the depth for a complete binary tree is O(logN).

binary-tree-left-sum-or-right-sum-larger Comparing Left and Right Branch of a Complete Binary Tree algorithms javascript recursive

binary-tree-left-sum-or-right-sum-larger

You can practice this problem at Hired.com which is a nice career platform for programmers.

–EOF (The Ultimate Computing & Technology Blog) —

推荐阅读:
国家食品药品监督管理总局正式挂牌  办公室白领防电脑辐射食品大盘点  春分节气饮食养生不同体质的食疗  问题奶粉不断涌现,奶粉监管怎么了?  保健食品营销骗局令人深恶痛绝  清明时节,可适当多吃寒性食物  饮食养生:越吃越聪明的健康食品  酒鬼酒被曝塑化剂严重超标事件  光明牛奶“酸败门”牛奶变质事件  古井贡酒用食用酒精勾兑生产事件 
评论列表
添加评论